The girth, odd girth, distance function,

and diameter of generalized Johnson graphs

John S. Caughman111Corresponding author<EMAIL_ADDRESS>AMS 2010 Subject
Classification: 05C12, Ari J. Herman, Taiyo S. Terada

_Department of Mathematics & Statistics_

_Portland State University, Portland, OR, USA_

###### Abstract

For any non-negative integers $v>k>i$, the generalized Johnson graph,
$J(v,k,i)$, is the undirected simple graph whose vertices are the $k$-subsets
of a $v$-set, and where any two vertices $A$ and $B$ are adjacent whenever
$|A\cap B|=i$. In this article, we derive formulas for the girth, odd girth,
distance function, and diameter of $J(v,k,i)$. In particular, let
$X=J(v,k,i)$. Assume $v\geq 2k$ and $(v,k,i)\not=(2k,k,0)$. For convenience,
abbreviate $\Delta=v-2k+2i$. We prove the following.

  1. (i)

The girth of $X$ is given by

$g(X)=\left\\{\begin{array}[]{ll}3&\hbox{if \, }v\geq 3(k-i);\\\ 4&\hbox{if \,
}v<3(k-i)\,\mbox{ and }\,(v,k,i)\not=(2k+1,k,0);\\\ 5&\hbox{if \,
}(v,k,i)=(5,2,0);\\\ 6&\hbox{if \,}(v,k,i)=(2k+1,k,0)\,\mbox{ and
}\,k>2.\end{array}\right.$

  2. (ii)

The odd girth of $X$ is given by

$og(X)=2\left\lceil\frac{k-i}{\Delta}\right\rceil+1.$

  3. (iii)

Let $A$ and $B$ be vertices of $X$ and let $x=|A\cap B|$. Then

$\text{dist}(A,B)=\left\\{\begin{array}[]{ll}3&\hbox{if \,
}x<\min\\{i,k-\Delta\\};\\\ \lceil\frac{k-x}{k-i}\rceil&\hbox{if \,
}k-\Delta\leq x<i;\\\
\min\\{2\lceil\frac{k-x}{\Delta}\rceil,2\lceil\frac{x-i}{\Delta}\rceil+1\\}&\hbox{if
\, }x\geq i.\end{array}\right.$

  4. (iv)

The diameter of $X$ is given by

$\text{diam}(X)=\left\\{\begin{array}[]{ll}\lceil\frac{k-i-1}{\Delta}\rceil+1&\hbox{if
\, }v<3(k-i)-1\text{ or }i=0;\\\ 3&\hbox{if \, }3(k-i)-1\leq v<3k-2i\text{ and
}i\neq 0;\\\ \lceil\frac{k}{k-i}\rceil&\hbox{if \, }v\geq 3k-2i\text{ and
}i\neq 0.\\\ \end{array}\right.$

Keywords girth; odd girth; generalized Johnson graph; odd graph; Kneser graph;
uniform subset graph

1\. Introduction

Fix any non-negative integers $v>k>i$. The generalized Johnson graph,
$X=J(v,k,i)$, is the undirected simple graph whose vertices are the
$k$-subsets of a $v$-set, and where any two vertices $A$ and $B$ are adjacent
whenever $|A\cap B|=i$. Generalized Johnson graphs were introduced by Chen and
Lih in [3] and have also been studied under the name uniform subset graphs.
Special cases include the Kneser graphs $J(v,k,0)$, the odd graphs
$J(2k+1,k,0)$, and the Johnson graphs $J(v,k,k-1)$.

In what follows, we derive formulas for the girth, odd girth, distance
function, and diameter of $J(v,k,i)$. Some special cases have been previously
determined. The classical Johnson graph $J(v,k,k-1)$ is well known to have
diameter $\min\\{k,v-k\\}$, and formulas for the distance and diameter of
Kneser graphs were proved in [9]. The diameter of $J(v,k,i)$ was studied in
[4]; however, a formula there gives incorrect values when $i>\frac{2}{3}k$, an
important case that includes the classical Johnson graphs. In this paper, we
extend and correct such expressions. Regarding odd girth, the Kneser graphs
are known to have odd girth $2\lceil\frac{k}{v-2k}\rceil+1$, as proved in [8],
which meets the bound given in [6, p.146], and which simplifies to $2k+1$ in
the case of the odd graphs. The Johnson graphs are distance-regular (see [2]
or [6]) but not triangle-free when $v>2$, so they have girth (and odd girth)
3.

We note that it is possible to extend the definition of $X=J(v,k,i)$ to
include cases allowed by the weaker inequalities $v\geq k\geq i$. However, $X$
is an empty graph when $k=i$ or $v=k$. If $v=2k$ and $i=0$, then $X$ is
isomorphic to the disjoint union of ${2k}\choose{k}$$/2$ copies of $K_{2}$.
Furthermore, by taking complements, the graphs $J(v,k,i)$ and
$J(v,v-k,v-2k+i)$ are easily seen to be isomorphic (see [7, p.9]). To simplify
the exposition, we will often refer to the following global definition.

Definition 1.1.  Fix any nonnegative integers $v>k>i$ and let $X=J(v,k,i)$
denote the corresponding generalized Johnson graph. Assume that $v\geq 2k$ and
$(v,k,i)\not=(2k,k,0)$. For convenience, we abbreviate $\Delta=v-2k+2i$.

Our assumptions imply that $\Delta>0$, and $\Delta>1$ unless
$(v,k,i)=(2k+1,k,0)$.

2\. Girth

Recall that the girth $g(X)$ of a graph $X$ is the length of the shortest
cycle in $X$. In this section we derive an expression for the girth of a
generalized Johnson graph. We begin with a lemma that characterizes when two
vertices have a common neighbor.

Lemma 2.1.  (Common Neighbor Condition) With reference to Definition 1, let
$A$ and $B$ be any vertices and let $x=|A\cap B|$. Then $A$ and $B$ have a
common neighbor if and only if $x\geq\max\\{k-\Delta,2i-k\\}$.

Proof.  Note $A$,$B$ have a common neighbor $C$ if and only if there exists
$s\in{\mathbb{Z}}$, such that every region in Figure 1 has nonnegative size.

Figure 1: Diagram for Lemma 1

By simplifying the resulting inequalities, we find that $A$ and $B$ have a
common neighbor if and only if there exists $s\in\mathbb{Z}$, such that

$\max\\{0,\;i+x-k,\;2i-k\\}\leq s\leq\min\\{x,\;i,\;v-3k+2i+x\\}.$

Such an integer $s$ exists if and only if the expression on the left side
above does not exceed the expression on the right side. Under our global
assumptions, this is equivalent to $x\geq\max\\{k-\Delta,2i-k\\}$. $\square$

The lemma above leads immediately to a condition for girth 3.

Lemma 2.2.  (Girth 3) With reference to Definition 1, the girth $g(X)=3$ if
and only if $v\geq 3(k-i)$.

Proof.  The graph $X$ contains a $3$-cycle iff there exist adjacent vertices
$A$ and $B$ that have a common neighbor. By Lemma 1, this occurs iff
$i\geq\max\\{k-\Delta,2i-k\\}$. Since $i\geq 2i-k$ holds in all $J(v,k,i)$
graphs, this condition is equivalent to $v\geq 3(k-i)$. $\square$

A sufficient condition for the girth to be at most $4$ is the existence of a
$4$-cycle.

Lemma 2.3.  (Girth 4) With reference to Definition 1, if
$(v,k,i)\not=(2k+1,k,0)$, then $g(X)\leq 4$.

Proof. We proceed in three cases.

Case 1: $i\geq 2$ or $v>2k+1$. In this case, we have $v\geq 2k-i+2$. So we can
find disjoint sets, $A_{1},A_{2},A_{3},A_{4}$, and $B_{1},B_{2},$ and $C$ such
that $|A_{1}|=|A_{2}|=|A_{3}|=|A_{4}|=1$, and $|B_{1}|=|B_{2}|=k-i-1$, and
$|C|=i$. Then, as in Figure 2, the following is a 4-cycle in $X$:

$A_{1}\cup B_{1}\cup C,\;\;\;A_{2}\cup B_{2}\cup C,\;\;\;A_{3}\cup B_{1}\cup
C,\;\;\;A_{4}\cup B_{2}\cup C.$

Figure 2: Diagram for Case 1 of Lemma 1

Case 2: $i=1$. In this case, since $v\geq 2k$, we can find disjoint sets
$A_{1},A_{2},A_{3},A_{4}$ and $B_{1},B_{2}$ such that
$|A_{1}|=|A_{2}|=|A_{3}|=|A_{4}|=1$ and $|B_{1}|=|B_{2}|=k-2$. Then, as
illustrated in Figure 3, the following is a 4-cycle in $X$:

$A_{1}\cup A_{2}\cup B_{1},\;\;\;A_{2}\cup A_{3}\cup B_{2},\;\;\;A_{3}\cup
A_{4}\cup B_{1},\;\;\;A_{4}\cup A_{1}\cup B_{2}.$

Figure 3: Diagram for Case 2 of Lemma 1

Case 3: $i=0$ and $v\leq 2k+1$. Recall that $v\geq 2k$. So either $v=2k$ or
$2k+1$, giving $(v,k,i)=(2k,k,0)$ or $(2k+1,k,0)$. Both are excluded by our
assumptions. $\square$

Combining the above lemmas, we obtain a general expression for the girth.

Theorem 2.4.  With reference to Definition 1, the girth of $X$ is given by

$g(X)=\left\\{\begin{array}[]{ll}3&\hbox{if \, }v\geq 3(k-i);\\\ 4&\hbox{if \,
}v<3(k-i)\,\mbox{ and }\,(v,k,i)\not=(2k+1,k,0);\\\ 5&\hbox{if \,
}(v,k,i)=(5,2,0);\\\ 6&\hbox{if \,}(v,k,i)=(2k+1,k,0)\,\mbox{ and
}\,k>2.\end{array}\right.$

Proof.  The first two cases follow from Lemmas 1 and 1. The remaining cases
are odd graphs, for which the girth is well-known. (See, for example, [2,
p.58].) $\square$

3\. Distance

In this section, we consider questions of distance. With reference to
Definition 1, we derive a general expression for the distance between two
vertices in terms of their intersection.

We begin with the distance between vertices whose intersection is less than
$i$.

Lemma 3.1.  With reference to Definition 1, let $A$ and $B$ be vertices and
let $x=|A\cap B|$. Suppose $x<i$. Then

${\rm dist}(A,B)=\left\\{\begin{array}[]{cl}3&\;\hbox{if \, }x<k-\Delta;\\\
{\displaystyle\left\lceil\frac{k-x}{k-i}\right\rceil}&\;\hbox{if \, }x\geq
k-\Delta.\end{array}\right.$

Proof. We proceed in three cases.

Case 1: $x<k-\Delta$. By Lemma 1 and $x<i$, dist$(A,B)\geq 3$. As in Figure 4,
let $A^{\prime}\subseteq A\setminus B$, such that $|A^{\prime}|=i-x$. Let
$B^{\prime}\subseteq B\setminus A$, such that $|B^{\prime}|=k-i$. Let
$C=A^{\prime}\cup(A\cap B)\cup B^{\prime}$. Then $|C|=k$, and $|A\cap C|=i$,
so $C$ is a vertex adjacent to $A$. Note that $|B\cap C|=k-i+x\geq k-\Delta$.
Also, since $x<k-\Delta$, we have $2i-k<-(v-2k)-x\leq 0$, so $|B\cap C|\geq
2i-k$. By Lemma 1, dist$(B,C)\leq 2$ and dist$(A,B)=3$ as desired.

Figure 4: Diagram for Case 1 of Lemma 1

Case 2: $x\geq k-\Delta$ and $x\geq 2i-k$. Since $x<i$, Lemma 1 implies
dist$(A,B)=2$. Also note that $k-i<k-x\leq 2(k-i)$, so
$\lceil\frac{k-x}{k-i}\rceil=2$, as desired.

Case 3: $x\geq k-\Delta$ and $x<2i-k$. In this case, $k-x>2(k-i)$. So there
exist positive integers $q,m$ such that $k-x=(q+1)(k-i)+m$ with $0<m\leq k-i$.
Let $C=A\cap B$. Then we can write $A$ and $B$ as disjoint unions

$A=A_{1}\cup\cdots\cup A_{q+2}\cup C\hskip 10.00002pt\mbox{and}\hskip
10.00002ptB=B_{1}\cup\cdots\cup B_{q+2}\cup C,$

where $|A_{j}|=|B_{j}|=k-i$ for $j\in\\{1,\ldots,q+1\\}$ and
$|A_{q+2}|=|B_{q+2}|=m$. Define

$X_{j}=(B_{1}\cup\cdots\cup B_{j})\cup(A_{j+1}\cup\cdots\cup A_{q+2})\cup C$

for each $j\in\\{1,\ldots,q\\}$. As in Figure 5, $A,X_{1},\ldots,X_{q}$ is a
path of length $q$. Note that $|X_{q}\cap B|=x+q(k-i)=i-m$. So now, by our
case assumptions,

$i>|X_{q}\cap B|=i-m\geq 2i-k>x\geq k-\Delta.$

By Lemma 1, we see that dist$(X_{q},B)=2$. So dist$(A,B)\leq
q+2=\lceil\frac{k-x}{k-i}\rceil$. On the other hand, since adjacent vertices
differ only by $k-i$ elements, dist$(A,B)\geq\lceil\frac{k-x}{k-i}\rceil$.
$\square$

Figure 5: Diagram for Case 3 of Lemma 1

It remains to consider the case when $|A\cap B|$ is greater than $i$. Before
we do so, the following result adapts Lemmas 1,2 in [5] to generalized Johnson
graphs.

Lemma 3.2.  With reference to Definition 1, let $A$ and $B$ be vertices and
let $x=|A\cap B|$. Suppose there is an $AB$-path of length $d$.

  1. (i)

If $d=2p$, then $p\geq\left\lceil\frac{k-x}{\Delta}\right\rceil.$

  2. (ii)

If $d=2p+1$, then $p\geq\left\lceil\frac{x-i}{\Delta}\right\rceil.$

Proof.  We argue by induction on $d$. If $d=0$, then $A=B$ so, $x=k$ and
$p=0\geq\lceil\frac{k-x}{\Delta}\rceil$. If $d=1$, then $x=i$, so
$p=0\geq\lceil\frac{x-i}{\Delta}\rceil$. If $d=2$, then by Lemma 1, $x\geq
k-\Delta$. Hence, $p=1\geq\lceil\frac{k-x}{\Delta}\rceil$. Now assume $d\geq
3$ and that the claim holds for all vertices joined by paths of length less
than $d$. We proceed in two cases.

Case 1: $d=2p$. Along the $AB$-path, there exists a vertex $C$ with an
$AC$-path of length $2(p-1)$ and a $BC$-path of length 2. By the inductive
hypothesis, $k-|A\cap C|\leq(p-1)\Delta$ and $k-|C\cap B|\leq\Delta$.
Therefore, $k-x=|A\setminus B|\leq|A\setminus C|+|C\setminus B|\leq p\Delta$.
Hence $p\geq\lceil\frac{k-x}{\Delta}\rceil$.

Case 2: $d=2p+1$. Along the $AB$-path, there exists a vertex $C$ that is
adjacent to $B$ and has an $AC$-path of length $2p$. By the inductive
hypothesis, $|A\setminus C|\leq p\Delta$. Therefore, $x-i=|A\cap
B|-i\leq|A\setminus C|+|B\cap C|-i\leq p\Delta$. Hence
$p\geq\lceil\frac{x-i}{\Delta}\rceil$. $\square$

The previous lemma implies a lower bound on the distance. The next result will
show that this bound is sharp.

Lemma 3.3.  With reference to Definition 1, let $A$ and $B$ be vertices and
let $x=|A\cap B|$. Suppose $x>i$. Then

${\textstyle{\rm
dist}(A,B)=\min\left\\{2\left\lceil\frac{k-x}{\Delta}\right\rceil,2\left\lceil\frac{x-i}{\Delta}\right\rceil+1\right\\}.}$
(1)

Proof.  When $x=k$ the result is trivial, so assume $x<k$. Let $C=A\cap B$ and
$D=\overline{A\cup B}$; it follows that $|C|=x$ and $|D|=v-2k+x$. There exist
non-negative integers $q,m$ such that $k-x=q\Delta+m$, with $0<m\leq\Delta$.
We can write A and B as disjoint unions $A=C\cup\\{a_{1},\ldots,a_{k-x}\\}$
and $B=C\cup\\{b_{1},\ldots,b_{k-x}\\}$.

If $q=0$, then $k-x=m\leq\Delta$, which implies $x\geq-v+3k-2i$. The right
side of (1) equals 2. Since $x>i$, we also have $x>2i-k$. By Lemma 1,
dist$(A,B)=2$ as desired.

Now, assume $q\geq 1$. For each $j\in\\{1,\ldots,q\\}$, let

$A_{j}=\\{a_{1},\ldots,a_{(j-1)\Delta+i}\\}\hskip 10.00002pt\mbox{and}\hskip
10.00002ptA_{j}^{\prime}=\\{a_{j\Delta+1},\ldots,a_{k-x}\\},$
$B_{j}=\\{b_{1},\ldots,b_{j\Delta}\\}\hskip 10.00002pt\mbox{and}\hskip
10.00002ptB_{j}^{\prime}=\\{b_{j\Delta-i+1},\ldots,b_{k-x}\\},$

and define

$X_{2j-1}=D\cup A_{j}\cup B_{j}^{\prime}\hskip 10.00002pt\mbox{and}\hskip
10.00002ptX_{2j}=C\cup B_{j}\cup A_{j}^{\prime}.$

Figure 6: Diagram for Lemma 1

Then, as in Figure 6, we see that $A,X_{1},\ldots,X_{2q}$ is a path of length
$2q$. Note that $|X_{2q}\cap B|=k-m\geq k-\Delta=-v+3k-2i$. Also, since $m\leq
k-x$, we have $|X_{2q}\cap B|\geq x>i\geq 2i-k$. So dist$(X_{2q},B)=2$ by
Lemma 1, and dist$(A,B)\leq 2q+2=2\lceil\frac{k-x}{\Delta}\rceil$.

Now, choose any $D^{\prime}\subseteq D$, $C^{\prime}\subseteq C$ satisfying
$|D^{\prime}|=|C^{\prime}|=x-i$. Let $A^{\prime}=(B\setminus C^{\prime})\cup
D^{\prime}$. Then $A^{\prime}$ is a vertex adjacent to $A$. Further,
$|A^{\prime}\cap B|=k-x+i>i$. By applying the previous argument to
$A^{\prime}$ and $B$, we have dist$(A^{\prime},B)\leq
2\lceil\frac{k-(k-x+i)}{\Delta}\rceil=2\lceil\frac{x-i}{\Delta}\rceil$.
Therefore dist$(A,B)\leq 2\lceil\frac{x-i}{\Delta}\rceil+1$.

By Lemma 1, it follows that
dist$(A,B)=\min\\{2\lceil\frac{k-x}{\Delta}\rceil,2\lceil\frac{x-i}{\Delta}\rceil+1\\}$.
$\square$

From the above results, we obtain a general formula for the distance between
two vertices.

Theorem 3.4.  With reference to Definition 1, let $A$ and $B$ be vertices and
let $x=|A\cap B|$. Then

$\text{dist}(A,B)=\left\\{\begin{array}[]{ll}3&\hbox{if \,
}x<\min\\{i,k-\Delta\\};\\\ \lceil\frac{k-x}{k-i}\rceil&\hbox{if \,
}k-\Delta\leq x<i;\\\
\min\\{2\lceil\frac{k-x}{\Delta}\rceil,2\lceil\frac{x-i}{\Delta}\rceil+1\\}&\hbox{if
\, }x\geq i.\\\ \end{array}\right.$ (2)

Proof.  Apply Lemmas 1 and 1. Note that when $x=i$, we have
dist$(A,B)=1=\min\\{2\lceil\frac{k-x}{\Delta}\rceil,2\lceil\frac{x-i}{\Delta}\rceil+1\\}$.
$\square$

4\. Diameter

In this section, we find the diameter of generalized Johnson graphs. We begin
with a well-known observation about the classical Johnson graphs $J(v,k,k-1)$
that is an easy corollary of Theorem 1.

Corollary 4.1.  With reference to Definition 1, assume $k=i+1$. Then

$\mbox{diam}(X)=k.$

Proof.  Fix any vertices $A,B$ and let $x=|A\cap B|$. Since $v\geq 2k$, we
have $k-\Delta\leq 1-i$. So $\min\\{i,k-\Delta\\}\leq 0$ and the first case in
(2) is impossible. If $x\geq i$, then $x=k$ or $k-1$, so $\mbox{dist}(A,B)=0$
or 1. And if $k-\Delta\leq x<i$ then the second case in (2) says
$\mbox{dist}(A,B)=k-x$ which ranges between 2 and $k$ as $x$ ranges between 0
and $i-1$. $\square$

The next result determines the maximum value of the expression in Lemma 1 when
we exclude the classical Johnson graphs.

Lemma 4.2.  With reference to Definition 1, assume $k>i+1$. Let

${\textstyle
f(x)=\min\left\\{2\left\lceil\frac{k-x}{\Delta}\right\rceil,2\left\lceil\frac{x-i}{\Delta}\right\rceil+1\right\\},}$

and let $\mathcal{I}=\\{i+1,\ldots,k\\}$. Then

$\max_{x\in\mathcal{I}}\,f(x)={\textstyle\left\lceil\frac{k-i-1}{\Delta}\right\rceil+1.}$

Proof.  Let $x\in\mathcal{I}$. There exist integers $\epsilon\in\\{0,1\\}$ and
$q,m\geq 0$ such that $k-i-1=(2q+\epsilon)\Delta+m$ and $0<m\leq\Delta$. We
prove $\max_{x\in\mathcal{I}}f(x)=2q+\epsilon+2$.

Let $x_{0}=(q+\epsilon)\Delta+i$. If $x>x_{0}$, then
$2\lceil\frac{k-x}{\Delta}\rceil\leq
2\lceil\frac{k-(x_{0}+1)}{\Delta}\rceil=2(q+1)\leq 2q+\epsilon+2$. If $x\leq
x_{0}$, then $2\lceil\frac{x-i}{\Delta}\rceil+1\leq
2\lceil\frac{x_{0}-i}{\Delta}\rceil+1=2(q+\epsilon)+1\leq 2q+\epsilon+2$.
Hence, $f(x)\leq 2q+\epsilon+2$.

Let $x_{1}=q\Delta+i+1+\epsilon(m-1)\in\mathcal{I}$. It follows that
$\lceil\frac{k-x_{1}}{\Delta}\rceil=q+\epsilon+1$ and
$\lceil\frac{x_{1}-i}{\Delta}\rceil=q+1$. Therefore,
$f(x_{1})=\min\\{2(q+\epsilon+1),2q+3\\}=2q+\epsilon+2$, and the result
follows. $\square$

We can apply the previous lemma to obtain the following corollary, which gives
the well-known diameter (see [9]) of the Kneser graphs $J(v,k,0)$.

Corollary 4.3.  [9, Theorem 1] With reference to Definition 1, assume $i=0$.
Then

$\mbox{diam}(X)={\textstyle\left\lceil\frac{k-1}{v-2k}\right\rceil+1.}$

Proof.  Fix any vertices $A,B$. Let $x=|A\cap B|$ and apply case $x\geq i$ in
(2). Since $i=0$, note that $\Delta=v-2k$. If $k=1$, then $X$ is complete, so
$\mbox{diam}(X)=1$, as desired. If $k>1$, Lemma 1 says the maximum value of
the distance function is $\left\lceil\frac{k-1}{v-2k}\right\rceil+1,$ as
desired. $\square$

We now present the general expression for the diameter. This theorem extends
and corrects previous claims found elsewhere (for example, [4]).

Theorem 4.4.  With reference to Definition 1, we have

$\text{diam}(X)=\left\\{\begin{array}[]{ll}\lceil\frac{k-i-1}{\Delta}\rceil+1&\hbox{if
\, }v<3(k-i)-1\text{ or }i=0;\\\ 3&\hbox{if \, }3(k-i)-1\leq v<3k-2i\text{ and
}i\neq 0;\\\ \lceil\frac{k}{k-i}\rceil&\hbox{if \, }v\geq 3k-2i\text{ and
}i\neq 0.\\\ \end{array}\right.$

Proof.  By Corollaries 1 and 1, the result holds when $i=0$ or $i=k-1$, so
assume $0<i<k-1$. We proceed in three cases.

Case 1: $v<3(k-i)-1$. In this case, $\lceil\frac{k-i-1}{\Delta}\rceil+1\geq
3$. Also, $3(k-i)>v\geq 2k$, so $\lceil\frac{k-i-1}{\Delta}\rceil+1\geq
3>\lceil\frac{k}{k-i}\rceil$. By Lemma 1 and Theorem 1, there exist vertices
$A,B$ such that dist$(A,B)=\lceil\frac{k-i-1}{\Delta}\rceil+1$. It follows
that diam$(X)=\lceil\frac{k-i-1}{\Delta}\rceil+1$, as desired.

Case 2: $3(k-i)-1\leq v<3k-2i$. In this case,
$\lceil\frac{k-i-1}{\Delta}\rceil+1\leq 2$. Also, $3k-2i>v\geq 2k$, so
$\lceil\frac{k}{k-i}\rceil\leq 2$. By Theorem 1, if $A,B$ are any disjoint
vertices, dist$(A,B)=3$, since $\min\\{i,k-\Delta\\}>0$. Hence, diam$(X)=3$,
as desired.

Case 3: $v\geq 3k-2i$. In this case, $\lceil\frac{k-i-1}{\Delta}\rceil+1\leq
2$. Also $k\leq\Delta$, so the first case in Theorem 1 does not occur. Since
$i>0$, we have $\lceil\frac{k}{k-i}\rceil\geq 2$. By Theorem 1, if $A,B$ are
any disjoint vertices, dist$(A,B)=\lceil\frac{k}{k-i}\rceil$. Hence
diam$(X)=\lceil\frac{k}{k-i}\rceil$, as desired. $\square$

5\. Odd Girth

With reference to Definition 1, Theorem 1 says that the girth of $X$ satisfies
$3\leq g(X)\leq 6$. When $g(X)=3$ or $5$, the odd girth equals the girth, so
$og(X)=3$ or $5$, respectively. We consider the cases of even girth separately
below. We will see that, in all cases, the odd girth is given by the following
expression:

$og(X)=2\left\lceil\frac{k-i}{\Delta}\right\rceil+1.$ (3)

Girth 6 case.

With reference to Definition 1, assume $g(X)=6$. Theorem 1 tells us that $X$
is an odd graph, with $(v,k,i)=(2k+1,k,0)$ for some integer $k>2$. In this
case, the odd girth equals $2k+1$, a result originally due to [8]. Observe
that, since $i=0$ and $\Delta=1$, this agrees with the expression in (3).
Because this value also follows readily from our previous results, we include
a proof here.

Lemma 5.1. [8, Cor. 11] With reference to Definition 1, assume $k>2$. Let
$X=J(2k+1,k,0)$. Then

$og(X)=2k+1.$

Proof.  Suppose $A_{1},A_{2},...,A_{2t+1}$ is any odd cycle in $X$. Then
dist$(A_{1},A_{3})=2$, so $|A_{1}\cap A_{3}|=k-1$ by Theorem 1. The cycle also
has a path of length $2t-1$ from $A_{3}$ to $A_{1}$, so $t\geq k$ by Lemma 1.
It remains to show that a closed walk of length $2k+1$ exists.

If $k=2d$ then $v=4d+1$. Let

$A=\\{1,...,2d\\},\quad B=\\{d+1,...,3d\\},\quad C=\\{2d+1,...,4d\\}.$

If $k=2d+1$ then $v=4d+3$. Let

$A=\\{1,...,2d+1\\},\quad B=\\{d+2,...,3d+2\\},\quad C=\\{2d+3,...,4d+3\\}.$

In both cases, $|A\cap B|=|B\cap C|=d$ and $|A\cap C|=0$. So, by Theorem 1,
dist$(A,B)=$ dist$(B,C)=k$, and dist$(A,C)=1$, as desired. $\square$

Girth 4 case.

With reference to Definition 1, assume $g(X)=4$. It is helpful to recall that
$\Delta>1$ unless $(v,k,i)=(2k+1,k,0).$ But $g(X)=4$, so Theorem 1 implies
that

$1<\Delta<k-i.$ (4)

To establish (3), it will help to have conditions to guarantee that a pair of
vertices are at distance $\lceil\frac{k-i}{\Delta}\rceil.$

Lemma 5.2.  With reference to Definition 1, assume $g(X)=4$. Let
$r=\lceil\frac{k-i}{\Delta}\rceil$. Fix any vertices $A$,$B$ and let $x=|A\cap
B|$. Then the following hold.

  1. (i)

If $r$ is odd and
$x\in\\{\lfloor\frac{k+i-\Delta}{2}\rfloor,\lceil\frac{k+i-\Delta}{2}\rceil\\}$,
then dist$(A,B)=r$.

  2. (ii)

If $r$ is even and
$x\in\\{\lfloor\frac{k+i}{2}\rfloor,\lceil\frac{k+i}{2}\rceil\\}$, then
dist$(A,B)=r$.

Proof.  (i). Assume $r$ is odd and
$x\in\\{\lfloor\frac{k+i-\Delta}{2}\rfloor,\lceil\frac{k+i-\Delta}{2}\rceil\\}$.
Write $r=2d+1$ so that

$2d<\frac{k-i}{\Delta}\leq 2d+1.$ (5)

Claim 1: $\left\lceil\frac{x-i}{\Delta}\right\rceil=d$. By (4), we know
$\Delta\geq 2$, so (5) implies
$2d-1+\frac{2}{\Delta}\leq\frac{k-i}{\Delta}\leq 2d+1.$ Subtract $1$ and
multiply by $\Delta/2$ to get
$\Delta(d-1)+1\leq\frac{k+i-\Delta}{2}-i\leq\Delta d.$ Now we have
$\Delta(d-1)+1\leq x-i\leq\Delta d.$ Dividing by $\Delta$ yields
$\left\lceil\frac{x-i}{\Delta}\right\rceil=d$, as claimed.

Claim 2: $x>i$. By (4), we know $\Delta<k-i$, and therefore $r>1$. This fact
implies $d>0$. By Claim 1, it now follows that $x>i$, as desired.

Claim 3: $\lceil\frac{k-x}{\Delta}\rceil\geq d+1$. To see this, note that
$\left\lceil\frac{k-x}{\Delta}\right\rceil+\left\lceil\frac{x-i}{\Delta}\right\rceil\geq\frac{(k-x)+(x-i)}{\Delta}=\frac{k-i}{\Delta}>2d,$
where the final inequality is from (5). By Claim 1, we have
$\lceil\frac{k-x}{\Delta}\rceil\geq d+1$, as desired.

Applying Claims 1-3 to Theorem 1, we have dist$(A,B)=2d+1$, proving (i).

(ii). Assume $r$ is even and
$x\in\\{\lfloor\frac{k+i}{2}\rfloor,\lceil\frac{k+i}{2}\rceil\\}$. Write
$r=2d$ so that

$2d-1<\frac{k-i}{\Delta}\leq 2d.$ (6)

Claim 1: $\left\lceil\frac{k-x}{\Delta}\right\rceil=d$. By (4), we know
$\Delta\geq 2$, so (6) implies
$2d-2+\frac{2}{\Delta}\leq\frac{k-i}{\Delta}\leq 2d.$ Multiply by $\Delta/2$
and simplify to obtain $\Delta(d-1)+1\leq k-\frac{k+i}{2}\leq\Delta d.$ Now we
have $\Delta(d-1)+1\leq k-x\leq\Delta d.$ Dividing by $\Delta$ yields
$\left\lceil\frac{k-x}{\Delta}\right\rceil=d$, as claimed.

Claim 2: $\lceil\frac{x-i}{\Delta}\rceil\geq d$. To see this, note that
$\left\lceil\frac{k-x}{\Delta}\right\rceil+\left\lceil\frac{x-i}{\Delta}\right\rceil\geq\frac{(k-x)+(x-i)}{\Delta}=\frac{k-i}{\Delta}>2d-1,$
where the final inequality is from (6). By Claim 1, we have
$\lceil\frac{x-i}{\Delta}\rceil\geq d$, as desired.

Claim 3: $x>i$. By (4), we know $\Delta<k-i$, and therefore $r>1$. This fact
implies $d>0$. By Claim 2, it now follows that $x>i$, as desired.

Applying Claims 1-3 to Theorem 1, we have dist$(A,B)=2d$, proving (ii).
$\square$

We now can prove a lower bound for the odd girth.

Lemma 5.3.  With reference to Definition 1, assume $g(X)=4$. Then

$og(X)\geq 2\left\lceil\frac{k-i}{\Delta}\right\rceil+1.$

Proof.  Assume $og(X)=2r+1$ and fix adjacent vertices $A,B$ on a
$(2r+1)$-cycle. Let $C$ be the vertex opposite edge $AB$ on that cycle, so
that dist$(A,C)=$ dist$(B,C)=r$. We will prove $r\geq\frac{k-i}{\Delta}$ in
two cases, depending on the parity of $r$.

Case $r=2d+1$. We claim $|A\cap C|\leq\Delta d+i$. If not, let $x=|A\cap C|$
and suppose $x\geq\Delta d+i+1$. Then by Theorem 1, since $r$ is odd,
$d=\lceil\frac{x-i}{\Delta}\rceil\geq\lceil\frac{\Delta
d+1}{\Delta}\rceil=d+1$, a contradiction. Similarly, $|B\cap C|\leq\Delta
d+i$. Therefore, $v-2k+i\geq|C\setminus(A\cup B)|\geq k-2(\Delta d+i)$. It
follows that $\Delta-i\geq k-2(\Delta d+i)$, which implies
$r\geq\frac{k-i}{\Delta}$.

Case $r=2d$. We claim $|A\cap C|\geq k-\Delta d$. If not, let $x=|A\cap C|$
and suppose $x<k-\Delta d$. Since $r$ is even and $x<k-\Delta$, Theorem 1
implies $2d=2\lceil\frac{k-x}{\Delta}\rceil$, a contradiction. Similarly,
$|B\cap C|\geq k-\Delta d$. But now $k=|C|\geq|A\cap C|+|B\cap C|-|A\cap
B|\geq 2(k-\Delta d)-i$, and therefore $r\geq\frac{k-i}{\Delta}$. $\square$

Lemma 5.4.  With reference to Definition 1, assume $g(X)=4$. Then

$og(X)=2\left\lceil\frac{k-i}{\Delta}\right\rceil+1.$

Proof.  Let $r=\lceil\frac{k-i}{\Delta}\rceil.$ Given Lemma 1, we must
construct a closed walk of length $2r+1$. We proceed in two cases, depending
on the parity of $r$.

Case $r=2d+1$. Let $x=\frac{k+i-\Delta}{2}$. By Theorem 1, we have $2k\leq
v<3(k-i)$, so $0\leq x\leq k-i$. Fix any adjacent vertices $A,B$. Choose
$A_{0}\subseteq A\setminus B$ and $B_{0}\subseteq B\setminus A$ with
$|A_{0}|=\lfloor x\rfloor$ and $|B_{0}|=\lceil x\rceil$. Let
$C_{0}=\overline{A\cup B}$, and $C=A_{0}\cup B_{0}\cup C_{0}$. Then
$|C|=\lfloor x\rfloor+\lceil x\rceil+(v-2k+i)=k$, so $C\in V(X)$. Also,
$|A\cap C|=\lfloor x\rfloor$ and $|B\cap C|=\lceil x\rceil$. By Lemma 1(i),
dist$(A,C)=$ dist$(B,C)=r$ and $X$ has a closed walk of length $2r+1$.

Case $r=2d$. Let $x=\frac{k+i}{2}$, and notice that $0\leq x-i\leq k-i$. Fix
any adjacent vertices $A,B$. Choose $A_{0}\subseteq A\setminus B$ and
$B_{0}\subseteq B\setminus A$ with $|A_{0}|=\lfloor x\rfloor-i$ and
$|B_{0}|=\lceil x\rceil-i$. Let $C_{0}=A\cap B$, and $C=A_{0}\cup B_{0}\cup
C_{0}$. Then $|C|=k$, so $C\in V(X)$. Also, $|A\cap C|=\lfloor x\rfloor$ and
$|B\cap C|=\lceil x\rceil$. By Lemma 1(ii), dist$(A,C)=$ dist$(B,C)=r$ and $X$
has a closed walk of length $2r+1$. $\square$

General case.

Theorem 5.5.  With reference to Definition 1, the odd girth of $X$ is given by

$og(X)=2\left\lceil\frac{k-i}{\Delta}\right\rceil+1.$ (7)

Proof.  By Theorem 1, the girth of $X$ satisfies $3\leq g(X)\leq 6$.

If $g(X)=3$, then $og(X)=3$. In this case, $v\geq 3k-3i$ by Theorem 1, so
$k-i\leq v-2k+2i$ and equality holds in (7).

If $g(X)=4$, then equality holds in (7) by Lemma 1.

If $g(X)=5$, then $og(X)=5$. In this case, $(v,k,i)=(5,2,0)$ by Theorem 1, so
equality holds in (7).

Finally, if $g(X)=6$, then $(v,k,i)=(2k+1,k,0)$ for some integer $k>2$ by
Theorem 1. But then $og(X)=2k+1$ by Lemma 1 and equality holds in (7).
$\square$

## References

  * [1] L.A. Agong, C. Amarra, J.S. Caughman, A.J. Herman, and T.S. Terada.  On the girth and diameter of generalized Johnson graphs.  Discrete Mathematics, 341(1):138–142, 2018.
  * [2] N. Biggs.  Algebraic Graph Theory.  Cambridge University Press, Cambridge, 1974.
  * [3] B.-L. Chen and K.-W. Lih.  Hamiltonian uniform subset graphs.  Journal of Combinatorial Theory B, 42:257–263, 1987.
  * [4] Y. Chen and W. Wang.  Diameters of uniform subset graphs.  Discrete Mathematics, 308:6645–6649, 2008.
  * [5] Y. Chen and Y. Wang.  On the diameter of generalized Kneser graphs.  Discrete Mathematics, 308:4276–4279, 2008.
  * [6] C. D. Godsil.  Algebraic Combinatorics.  Chapman and Hall, New York, 1993.
  * [7] C. D. Godsil and G. Royle.  Algebraic Graph Theory.  Springer-Verlag, New York, 2001.
  * [8] S. Poljak and Zs. Tuza.  Maximum bipartite subgraphs of Kneser graphs.  Graphs Combin., 3:191–199, 1987.
  * [9] M. Valencia-Pabon and J.-C. Vera.  On the diameter of Kneser graphs.  Discrete Mathematics., 305:383–385, 2005.


# On points avoiding measures

Piotr Borodulin–Nadzieja  Mathematical Institute, University of Wrocław, pl.
Grunwaldzki 2, 50-384 Wrocław, Poland<EMAIL_ADDRESS>and  Artsiom
Ranchynski  Mathematical Institute, University of Wrocław, pl. Grunwaldzki 2,
50-384 Wrocław, Poland<EMAIL_ADDRESS>
###### Abstract.

We say that an element $x$ of a topological space $X$ avoids measures if for
every Borel measure $\mu$ on $X$ if $\mu(\\{x\\})=0$, then there is an open
$U\ni x$ such that $\mu(U)=0$. The negation of this property can viewed as a
local version of the property of supporting a strictly positive measure. We
study points avoiding measures in the general setting as well as in the
context of $\omega^{\ast}$, the remainder of Stone-Čech compactification of
$\omega$.

###### Key words and phrases:

P-points, weak P-points, strictly positive measures, Stone spaces

###### 2010 Mathematics Subject Classification:

Primary: 03E05, 03E35. Secondary: 03E75, 28E15.

The first author was supported by the National Science Centre, Poland under
the Weave-UNISONO call in the Weave programme 2021/03/Y/ST1/00124.

##  1\. Introduction

We say that a topological space $X$ is homogenuous if for every $x,y\in X$,
there is an autohomeomorphism $h\colon X\to X$ such that $h(x)=y$. For many
years, one of the most important problems in set theoretic topology was to
find a concrete reason why $\omega^{\ast}=\beta\omega\setminus\omega$, the
space of non-principal ultrafilters on the set of positive integers $\omega$,
is not homogenuous. Zdenék Frolik showed [11] that $\omega^{\ast}$ is not
homogenuous, but he has not indicated any points witnessing the lack of
homogeneity. So, the problem of finding a ’honest proof’ (using the words of
Eric van Douwen, see [8]) of non-homogeneity was still open.

In 1956 Walter Rudin defined the notion of P-point, see [17]. In the
topological setting, a point $x\in X$ is a P-point if every $G_{\delta}$
containing $x$ has nonempty interior containing $x$. It is easy to construct
P-points in $\omega^{\ast}$ under the assumption of Continuum Hypothesis and
it is also easy to see that there are ultrafilters which are not P-points. So,
under CH the problem of witnesses for non-homogeneity of $\omega^{\ast}$ is
settled.

One can construct P-points in $\omega^{\ast}$ under several axioms and it
seems that for some time mathematicians believed that P-points do exist in
ZFC. Surprisingly, Saharon Shelah constructed a model in which $\omega^{\ast}$
does not have any P-points, see [24]. So, Rudin’s approach does not work
without additional axioms.

Kenneth Kunen noticed in [14], that the property of being a P-point can be
relaxed to a slightly weaker one: we say that a point $x\in X$ is a weak
P-point if $x\notin\overline{C}$ for any countable $C\subseteq X$ which does
not contain $x$. Clearly, $\omega^{\ast}$ contain many points which are not
weak P-points (just take a countable subset of $\omega^{\ast}$ and consider
its closure). Actually, it is still not easy to show that there are weak
P-points in ZFC, directly. But, Kunen defined a stronger notion of
$\mathfrak{c}$-OK-points, and showed that that $\mathfrak{c}$-OK-points do
exist without any additional axioms, [15]. So, the problem of finding
witnesses of non-homogeneity was finally solved.

In this article, we define a seemingly new topological property which may be
interesting in this context. We say that a point $x\in X$ avoids measures, if
$x$ is not in the support of any measure $\mu$ such that $\mu(\\{x\\})=0$.
Recall that a support of a probability (Radon) measure $\mu$ is a smallest
closed set $K$ such that $\mu(K)=1$. Notice that this property is weaker than
the property of being a P-point: if $x$ is a P-point and $\mu(\\{x\\})=0$,
then we may find a sequence of open neighbourhoods $(U_{n})$ of $x$ such that
$\mu(U_{n})<1/n$. But then there is an open set $U\ni x$ such that $U\subseteq
U_{n}$ for each $n$. So, $\mu(U)=0$ and thus $x$ is not in the support of
$\mu$.

We are interested in this property because of two reasons.

First, we may consider its natural modifications: property of avoiding non-
atomic measures and property of avoiding purely atomic measures. It turns out
that the property of being a weak P-point can be stated in the language of
measures: a point is a weak P-point if and only if it avoids purely atomic
measures. It is natural to ask what is the connection between weak P-points
and points avoiding non-atomic measures. In Section 4 we present some results
along these lines in the general context. I.e., we show that these properties
are orthogonal althought the appropriate witnesses are not always cheap. We
show that the Stone space of the measure algebra contains a weak P-point and
that certain separable space constructed by Simon contains points avoiding
non-atomic measures. Then, in Section 5, using these results we present
examples of weak P-points which does not avoid measures and vice versa.

The second reason why we study ultrafilters avoiding measures goes back to the
question of witnesses for non-homogeneity of $\omega^{\ast}$. Kunen’s
construction of $\mathfrak{c}$-OK-point is quite involved. There is no easier
ZFC construction producing weak P-points known so far. But perhaps there is an
easier construction of an ultrafilter avoiding non-atomic measures. Note that
we can always define a non-atomic measure on $\omega^{\ast}$. One can define
such a measure explicitly, extending the asymptotic density along an
ultrafilter, see e.g. [21]. Or we can use a theorem of Rudin saying that a
compact space does not admit a non-atomic measure if and only if it is
scattered (see [18] and [16]). So, if we are able to show in ZFC that there is
an ultrafilter avoiding non-atomic measures, then we would have another
witness for non-homogeneity of $\omega^{\ast}$.

While trying to construct a point avoiding non-atomic measures, we came up
with a new notion: ultrafilter diagonalizing trees along ideals on
$2^{\omega}$. Using this property we were able to construct ultrafilters
avoiding measures, which are not P-points (at least under $CH$). Then we have
realized that this notion coincides with Baumgartner’s measure zero
ultrafilters. This gives us several examples of ultrafilters avoiding non-
atomic measures (using results of Baumgartner and Brendle) but also shows that
this approach cannot work in ZFC (as Shelah proved that consistently there are
non measure zero ultrafilters).

In Section 7 we show that the property of being a Q-point does not imply
avoiding non-atomic measures. The last section is devoted to open problems.

##  2\. Acknowledgements

We are grateful to Jan van Mill for reading a preliminary version of this
article and for sharing with us the proof of Theorem 4.7.

##  3\. Preliminaries

By a _measure_ on a Boolean algebra $\mathcal{B}$ we will mean a finitely
additive probability measure (i.e. such that $\mu(1_{\mathcal{B}})=1$). By a
measure on a topological space $X$ we will mean a $\sigma$-additive Radon
probability measure on $Bor(X)$. In particular, we assume that measures on
topological spaces are inner regular with respect to compact sets and outer
regular with respect to open sets.

######  Proposition 3.1.

Every measure $\mu$ on a Boolean algebra $\mathcal{P}(\omega)/fin$ can be
uniquely extended to a ($\sigma$-additive, Radon) measure on the Stone space
$St(\mathcal{P}(\omega)/fin)$.

Hence, there is a bijective correspondence between finitely-additive measures
on $\mathcal{P}(\omega)/fin$ and ($\sigma$-additive, Radon) measures on
${\omega}^{\ast}$.

A measure $\mu$ on a space $X$ is non-atomic if $\mu(\\{x\\})=0$ for every
$x\in X$.

A measure $\mu$ on a Boolean algebra $\mathcal{B}$ is _non-atomic_ (sometimes
called also _strongly continuous_) if for every $\varepsilon>0$ there exists a
finite partition $\\{P_{0},\dots,P_{n}\\}$ of unity with
$\mu(P_{i})<\varepsilon$ for each $i\leq n$. Note that a measure $\mu$ on a
Boolean algebra $\mathcal{B}$ is non-atomic if and only if its extension to
$St(\mathbb{B})$ is non-atomic.

A measure on a topological space $X$ is _purely atomic_ if $\mu$ is a
countable weighted sum of 0-1 measures.

A support of a measure $\mu$ on a space $X$ is $supp(\mu)=\bigcap\\{C\subseteq
X\colon\text{C is closed and }\mu(C)=1\\}$. If the measure is inner regular
with respect to compact sets, then $\mu(supp(\mu))=1$, see [10, 411N (d)].

######  Definition 3.2.

A point $x\in X$ _avoids measures_ if whenever $\mu$ is a measure on $X$ such
that $\mu(\\{x\\})=0$, then $x$ does not belong to the support of $\mu$.

We can consider points avoiding some specific type of measures. We will be
particularly interested in avoiding non-atomic measures so it will be
convenient to introduce the following notation.

######  Definition 3.3.

A point is a $\mu$-point if it avoids non-atomic measures.

A topological space has the _countable chain condition_ (is ccc, in short) if
it does not contain an uncountable family of pairwise disjoint open sets. By
$\mathbb{B}$ we denote the _measure algebra_ , i.e. the Boolean algebra
$\mathrm{Bor}(2^{\omega})/_{\mathcal{N}}$, where $\mathcal{N}$ denotes the
$\sigma$-ideal of Lebesgue measure zero sets. For $\kappa\geq\omega$ by
$\mathbb{B}_{\kappa}$ we mean the Boolean algebra
$\mathrm{Bor}(2^{\kappa})/_{\lambda_{\kappa}=0}$, where $\lambda_{\kappa}$ is
the standard Haar measure on $2^{\kappa}$.

For $A,B\subseteq\omega$, we write $A\subseteq^{\ast}B$ if $A\setminus B$ is
finite and $A=^{\ast}B$ if $A\triangle B$ is finite.

The Stone-Čech compactification of the non-negative integers
$\beta\omega=St(\mathcal{P}(\omega))$ is the Stone space of the Boolean
algebra $\mathcal{P}(\omega)$. By $\omega^{\ast}$ we denote the remainder of
Stone-Čech compactification of $\omega$, i.e.
$\omega^{\ast}=St(\mathcal{P}(\omega)/fin))$.

If $X\subseteq\omega$, then by $[X]$ we will denote the clopen subset of
$\beta\omega$ (or of $\omega^{\ast}$) induced by $X$, i.e.
$[X]=\\{x\in\beta\omega\colon X\in x\\}$. Similarly, if $v\in 2^{<\omega}$,
then by $[v]$ we will denote the clopen subset of $2^{\omega}$ induced by $v$:
$[v]=\\{x\in 2^{\omega}\colon x\mbox{ extends }v\\}$.

######  Definition 3.4.

A point $p\in X$ is a _$P$ -point_ if for every countable family of
neighbourhoods $\\{U_{n}\colon n\in\omega\\}$ of $p$ there exists open set $U$
such that $p\in U\subseteq\bigcap\limits_{n}U_{n}$.

######  Theorem 3.5 (W. Rudin, [17]).

Under (CH) there exists a $P$-point in $\beta\omega$.

It is also known that there is a model without $P$-points, see [24]. However,
in ZFC there exist points with slightly weaker property.

######  Definition 3.6.

A point $p\in X$ is a _weak $P$-point_ if $p$ is not a limit point of any
countable subset of $X\setminus\\{p\\}$.

We say that a closed subset $F\subseteq X$ is a _weak $P$-set_ if whenever $C$
is a countable set disjoint with $F$, we have $\overline{C}\cap F=\emptyset$.

##  4\. Results about general topological spaces

We say that a compact space $K$ supports a measure $\mu$ if $\mu(U)>0$ for
every nonempty open $U\subseteq K$ (or, equivalently, if $K$ is the support of
$\mu$). The property of _not_ avoiding measures is in a sense the _local_
version of the property of supporting a measure. E.g. if a space supports a
measure, then of course none of its point can avoid measures. We will show now
that this implication cannot be reversed, i.e. that there is a space which
does not support a measure, but which does not contain $\mu$-points, and so
_locally_ it supports a measure everywhere.

######  Proposition 4.1.

There is a space without strictly positive measure, and without points
avoiding measures.

###### Proof.

Let $X_{\alpha}=[0,1]$ for every $\alpha\in\omega_{1}$ and let
$X=\bigcup_{\alpha\in\omega_{1}}X_{\alpha}$ be the disjoint union of those
intervals. Let $K=X\cup\\{\infty\\}$ be the one-point compactification of $X$.

Clearly, $K$ does not satisfy $ccc$ and so there is no measure $\mu$ such that
$supp(\mu)=K$.

For every $\alpha\in\omega_{1}$ let $\lambda_{\alpha}$ be the Lebesgue measure
supported by $X_{\alpha}$ and let $\lambda_{\omega}$ be defined by

$\lambda_{\omega}=\sum_{n\in\omega}\frac{1}{2^{n}}\lambda_{n}.$

For every point $x_{0}\in X$ there is $\alpha\in\omega_{1}$ such that
$x_{0}\in X_{\alpha}$ and so $x_{0}\in\mathrm{supp}(\lambda_{\alpha})$.

By the definition of the one point compactification, for every open
$U\subseteq K$, if $\infty\in U$ then $X_{\alpha}\subseteq U$ for cofinitely
many $\alpha\in\omega_{1}$. Hence
$\infty\in\overline{(\bigcup_{n\in\omega}X_{n})}$ and so
$\infty\in\mathrm{supp}(\lambda_{\omega})$. ∎

We proceed with a fact which shows that the notion of avoiding measures is, in
a sense, generalization of the P-point property.

######  Proposition 4.2.

If $p$ is a P-point, then $p$ avoids measures.

###### Proof.

If $p$ is a P-point and $\mu$ is a measure such that $\mu(\\{p\\})=0$, then we
can find a decreasing sequence $(U_{n})$ of open neighborhoods of $p$ such
that $\mu(U_{n})<1/n$. There is $U\ni p$ such that $U\subseteq U_{n}$ for
every $n$ and so $\mu(U)=0$. Hence $x\notin\mathrm{supp}(\mu)$. ∎

######  Remark 4.3.

Although we have promised to deal only with Radon measures, when talking about
measures on topological spaces, let us make a remark that the above
proposition may be no longer true, if $\mu$ is not outer regular. Indeed,
consider $X=\omega_{1}+1$, $p=\omega_{1}$, and let $\mu$ be the Dieudonné’s
measure (see [10, 411Q]). Then $p$ is a P-point, $supp(\mu)=\\{p\\}$ and
$\mu(\\{p\\})=0$.

Since the notion of weak P-point also generalized P-pointness, it is natural
to ask how the points avoiding measures and weak P-points are related. It
turns out that weak P-points can be defined in terms of avoiding measures.

######  Proposition 4.4.

A point $p$ is a weak P-point if and only if it avoids purely atomic measures.

###### Proof.

Notice that since every inner regular 0-1 measure can be expressed as a Dirac
delta measure, $\mu$ on a topological space $X$ is purely atomic if and only
if it is of the form $\mu=\sum_{n\in\omega}a_{n}\delta_{x_{n}}$ for some
$a_{n}\geq 0$, $x_{n}\in X$, $\sum a_{n}=1$.

Suppose that $p$ is not a weak P-point and so that there is $C=\\{c_{n}\colon
n\in\omega\\}\subseteq X\setminus\\{p\\}$ such that $p\in\overline{C}$. Define
$\mu=\sum_{n}2^{-n}\delta_{c_{n}}$. Then $\mu(\\{p\\})=0$, and if $U$ is a
neighbourhood of $p$, then there is $n_{0}$ such that $c_{n_{0}}\in U$. Hence
$\mu(U)\geq 2^{-n_{0}}\delta_{c_{n_{0}}}(U)=2^{-n_{0}}>0$ and so $p\in
supp(\mu)$.

Suppose that $p$ does not avoid purely atomic measures, i.e. there is
$\mu=\sum_{n}a_{n}\delta_{c_{n}}$ for appropriate $(a_{n})$ and $(c_{n})$ such
that $\mu(\\{p\\})=0$ and $p\in supp(\mu)$. As $\mu(\\{p\\})=0$ we have that
$p\neq c_{n}$ for every $n\in\omega$. $p\in supp(\mu)$, for every
neighbourhood $U$ of $p$ we have $\mu(U)>0$. Hence, there is $n$ such that
$\delta_{c_{n}}(U)>0$ and so $c_{n}\in U$. Finally, $p\in\overline{C}$, where
$C=\\{c_{n}\colon\ n\in\omega\\}$. ∎

If $X$ is a scattered space, then by [18] every measure on $X$ is purely
atomic. So, if $X$ is scattered then $x\in X$ avoids measures if and only if
$x$ is a weak P-point.

######  Example 4.5.

Consider $X=\omega_{1}+1$ as the ordered topological space. It is scattered,
so every measure on $X$ is purely atomic. Hence, $\omega_{1}$ (as a point in
$X$) avoids measures.

However, there are both examples of spaces containing weak P-points but no
$\mu$-points and vice versa.

First of all, notice the following simple fact.

######  Proposition 4.6.

If $K$ is separable, and $x\in K$ is not isolated, then $x$ is not a weak
P-point.

Now we will show that the Stone space of the measure algebra contains a weak
P-point. We are grateful to Jan van Mill for presenting us the following
proof. It is an easy consequence of his theorem but it seems that it was not
stated explicitly in the literature. Of course none of the points in the Stone
space of the measure algebra can avoid the Lebesgue measure. So, it does not
contain a $\mu$-point.

Recall that if $K$ is the Stone space of the measure algebra $\mathbb{B}$ and
$\lambda$ is the standard measure on $K$, then $\lambda$ is inner (and outer)
regular with respect to clopen subsets. Also, $\mathbb{B}$ is homogeneous, in
the sense that $\\{A\in\mathbb{B}\colon A\subseteq B\\}$ is isomorphic to
$\mathbb{B}$ for each non-zero $B\in\mathbb{B}$. Consequently, if $L\subseteq
K$ is separable, then $\lambda(L)=0$ (as $K$ is not separable). For basic
properties of $K$ and $\lambda$, see e.g. [12, Section 24].

######  Theorem 4.7.

There is a weak P-point in the Stone space of the measure algebra
$\mathbb{B}$.

###### Proof.

Let $K=\mathrm{St}(\mathbb{B})$.

Let $(C_{n})$ be a family of pairwise disjoint clopens of $K$ such that
$\bigcup_{n}C_{n}$ is dense in $K$. Let $X=\bigcup_{n}C_{n}$. For $n\in\omega$
let $\mathcal{F}_{n}$ be the family defined by

$\mathcal{F}_{n}=\\{F\subseteq C_{n}\colon F\mbox{ is clopen and
}\lambda(C_{n}\setminus F)<\lambda(C_{n})/(n+1)\\}$

and notice that for each $n$ the family $\mathcal{F}_{n}$ is $n$-linked.

Let

$\mathcal{F}=\\{F\subseteq X\colon F\cap C_{n}\in\mathcal{F}_{n}\mbox{ for
each }n\\}.$

Then $\mathcal{F}$ is a filter on the Boolean algebra of clopen subsets of $X$
and by [23, Theorem 2.5] it can be extended to an ultrafilter $x\in\beta X$
which is a weak P-point in $X^{\ast}$.

Since $K$ is extremely disconnected, we have $K=\beta X$ and so $x\in K$. Now,
suppose that $N$ is a countable subset of $K$. We want to show that
$x\in\overline{N}$ and we may assume that either $N\subseteq X$ or $N\subseteq
K\setminus X=X^{\ast}$. Suppose, first, that $N\subseteq X^{\ast}$. Then
$x\notin\overline{N}$ as $x$ is a weak P-point of $X^{\ast}$. If $N\subseteq
X$, then there is $F\in\mathcal{F}$ such that $\overline{N}\cap F=\emptyset$.
Indeed, $\lambda(\overline{N})=0$ (see the remarks above) and so, by
regularity of $\lambda$ with respect to clopens, for every $n$ we can pick
$F_{n}\in\mathcal{F}_{n}$ such that $F_{n}\cap\overline{N}=\emptyset$. Then
$F=\bigcup_{n}F_{n}\in\mathcal{F}$ and $F\cap\overline{N}=\emptyset$. Hence
$x\notin\overline{N}$. ∎

######  Theorem 4.8.

There is a space $X$ which is separable (and so, there is no weak P-point in
$X$) but which contains $\mu$-point (in fact, a dense set of $\mu$-points).

###### Proof.

By [19], see also [9] there is a separable space $X$ with a countable, dense,
dense-in-itself subset $H\subseteq X$, which is a P-set in X. Given a non-
atomic measure $\mu$, since $H$ is countable, we have $\mu(H)=0$. By the same
argument as in the proof of Proposition 4.2 we can find a neighbourhood $U$ of
$H$ such that $\mu(U)=0$. Hence every point of $H$ is a $\mu$-point. Since $X$
is separable, there are no weak P-points. ∎

######  Remark 4.9.

In fact there is a ’simpler’ (or, at least, more classical) example of a space
containing a $\mu$-point which is not a weak P-point. Namely, $\beta\omega$
contains a non-isolated point which is a $\mu$-point (and which is not a weak
P-point because of separability of $\beta\omega$). We will come back to this
fact in the next section, armed with additional notions and facts.

We finish this section with some general results bonding the existence of weak
P-points and $\mu$-points.

######  Lemma 4.10.

A $\mu$-point cannot be a limit point of a countable set of non$-\mu$-points.

###### Proof.

Suppose that a set $A=\\{a_{n}\colon n\in\omega\\}$ is countable and none of
$a_{n}$ is a $\mu$-point. Assume that $p\in\overline{A}$. We will show that
$p$ does not avoid non-atomic measures.

Let ${\mu}_{n}$ be a non-atomic measure such that
$a_{n}\in\mathrm{supp}(\mu_{n})$. Define

$\mu=\sum_{n\in\omega}\frac{1}{2^{n}}{\mu}_{n}.$

Since $p\in\overline{A}$, for every open $U$ if $p\in U$, then there is
$n_{0}\in\omega$ such that $a_{n_{0}}\in U$. Then $\mu(U)\geq
2^{-n_{0}}{\mu}_{n_{0}}(U)>0$ and so $\mu(U)>0$ for every neighbourhood $U$ of
$p$. Hence $p\in\mathrm{supp}(\mu)$. ∎

######  Proposition 4.11.

If a compact space $K$ contains a $\mu$-point, then it contains a point which
is $\mu$\- and weak P- simultaneously (so, a point which avoids all measures),
or a countable, dense-in-itself subspace of $\mu$-points.

###### Proof.

Suppose there is at least one $\mu$-point $p\in X$, and that all $\mu$-points
in $X$ are not weak P-points. We inductively construct the subspace with
desired property. Let $A_{0}=\\{p\\}$ and $p$ is $\mu$-point. Suppose
$A_{i}=\\{a_{i}^{n}\colon n\in\omega\\}$ is constructed and consists of
$\mu$-points. For every $n$, as $a_{i}^{n}$ is a $\mu$-point, by the
assumption and by Lemma 4.10, there is a countable set $A_{i+1}^{n}$ of
$\mu$-points, such that $a_{i}^{n}\in\overline{A_{i+1}^{n}}$. Let
$A_{i+1}=\bigcup_{n\in\omega}A_{i+1}^{n}$. By the construction,
$A_{i}\subseteq\overline{A_{i+1}}$.

Let $A=\bigcup_{i\in\omega}A_{i}$. Then $A$ is a countable dense-in-itself set
of $\mu$-points. ∎

The last result will use some forcing (but without going into forcing
technicalities). Let us first make some general comments. Consider a model $M$
and its forcing extension $M[G]$. Let $\mathbb{A}$ be a Boolean algebra, an
element of the model $M$. Then $\mathbb{A}$ is also an element of $M[G]$. If
$x$ is an element of the Stone space of $\mathbb{A}$, then it is still an
element of the Stone space of $\mathbb{A}$ in $M[G]$. Typically the Stone
space of $\mathbb{A}$ computed in $M[G]$ will contain more elements and, in
general, the Stone space of $\mathbb{A}$ in $M[G]$ may have different
topological properties than the Stone space of $\mathbb{A}$ in $M$.

######  Proposition 4.12.

Suppose $\mathbb{A}$ is a Boolean algebra and $K$ is its Stone space. If $x\in
K$ does not avoid measures, then there is $\kappa$ such that
$\mathbb{B}_{\kappa}$ forces that $x$ is not a weak P-point in
$St(\mathbb{A})$.

###### Proof.

Let $\mathbb{A}$, $K$ and $x\in K$ be as above. Let $\mu$ be the measure on
$K$ such that $x\in F=\mathrm{supp}(\mu)$. By the Stone duality, there is a
Boolean algebra $\mathbb{A}^{\prime}$ such that $St(\mathbb{A}^{\prime})=F$
and there is a Boolean homomorphism
$\varphi\colon\mathbb{A}\to\mathbb{A}^{\prime}$ which is onto. Also, as $x\in
K$, $x$ extends (as an ultrafilter) the filter dual to the kernel of
$\varphi$. Since $\mathbb{A}^{\prime}$ supports a measure, by [13], there is
$\kappa$ such that $\mathbb{B}_{\kappa}$ forces that the Stone space
$K^{\prime}$ of $\mathbb{A}^{\prime}$ (computed in the extension) is
separable. The mapping $\varphi$ belongs to the extension, so in the extension
$x\in K^{\prime}$. Hence, it is not a weak P-point. ∎

##  5\. $\mu$-points versus weak P-points in $\omega^{\ast}$

In this section we consider the relationship between weak P-points and
$\mu$-points in $\omega^{\ast}$. We begin with a rather easy result: there are
points in $\omega^{\ast}$ which are neither weak P-points nor $\mu$-points.
Then we will show how to use Kunen’s $\mathfrak{c}$-OK-points to avoid all
measures (so to produce points which are both weak P-points and $\mu$-points).
Then we consider the following natural question: if a point
$x\in\omega^{\ast}$ avoids non-atomic measures, should it avoid also purely-
atomic ones (and so should it be a weak $P$-point) and vice versa?

######  Proposition 5.1.

There is an ultrafilter which is neither $\mu$-point nor a weak P-point.

###### Proof.

By [16] there is a non-atomic measure $\mu$ on $\omega^{\ast}$. Let $C$ be a
countable discrete subset of the support of $\mu$ and let
$x\in\overline{C}\setminus C$. Then $x$ is not a weak P-point (which is
witnessed by $C$) and $x$ does not avoid the measure $\mu$. ∎

The easiest example of a point of $\omega^{\ast}$ which avoids all measures
(and so it is both a $\mu$-point and a weak P-point) is a P-point (see
Proposition 4.2). Consistently, there are no P-points but nevertheless the
points avoiding measures do exist in ZFC.

######  Theorem 5.2.

There is a point which is a weak P-point and $\mu$-point simultaneously (and
so it avoids all measures).

To prove the above we will use so called $\mathfrak{c}$-OK point introduced by
Kunen in [15]. Kunen proved that $\mathfrak{c}$-OK-points cannot belong to a
closure of any ccc set (not containing the point itself). The above theorem is
an immediate consequence of this fact. We will enclose Kunen’s proof for the
readers convenience.

######  Definition 5.3.

A set $S\subseteq X$ is a _$\kappa$ -OK set_ if for every countable collection
$\\{U_{n}\colon n\in\omega\\}$ of neighbourhoods of $S$ there is a family of
$\kappa$ many neighbourhoods $\\{V_{\alpha}\colon\alpha<\kappa\\}$ (called a
refinement system of $\\{U_{n}\colon n\in\omega\\}$) such that for every
finite $n$ and $\alpha_{0}\dots\alpha_{n-1}$ we have
$V_{\alpha_{0}}\cap\dots\cap V_{\alpha_{n-1}}\subseteq U_{n}$. We say that a
point $p$ is a _$\kappa$ -OK point_ if $\\{p\\}$ is a $\kappa$-OK set.

######  Theorem 5.4 (Kunen).

There are $\mathfrak{c}$-OK-points in $\omega^{\ast}$.

The crucial fact connecting $\kappa$-OK-points with the points avoiding
measures is the following:

######  Theorem 5.5 (Kunen).

Suppose $X$ is a $T_{3}$ ccc space. Let $p\in X$ be a non isolated point. Then
$p$ is not $\omega_{1}$-OK.

###### Proof.

First, notice that if $p$ is as above, then $p$ is not a P-point. Otherwise we
could find a family $\\{U_{\alpha}\colon\alpha<\omega_{1}\\}$ of
neighbourhoods of $p$, such that $cl(U_{\beta})$ is a proper subset of
$U_{\alpha}$ whenever $\alpha<\beta$. But then
$\\{U_{\alpha}\setminus\overline{U_{\alpha+1}}:\alpha<\omega_{1}\\}$ would
contradict the ccc property.

Now, let $\\{U_{n}:\ n\in\omega\\}$ be a family of open neighborhoods of $p$
such that

$p\not\in\mathrm{Int}\left(\bigcap\limits_{n}\overline{U_{n}}\right).$

Let $\\{V_{\alpha}:\alpha<\omega_{1}\\}$ be a refinement system for
$\\{U_{n}:n\in\omega\\}$. For each $\alpha<\omega_{1}$, there is $n\in\omega$
such that $V_{\alpha}\setminus\overline{U_{n}}\neq\emptyset$, so fix
$n\in\omega$ so that $B=\\{\alpha<\omega_{1}:\
V_{\alpha}\setminus\overline{U_{n}}\neq\emptyset\\}$ is uncountable. For
$\alpha\in B$, let $W_{\alpha}=V_{\alpha}\setminus\overline{U_{n}}$. Then
$W_{\alpha}$ are non-empty, but any $n$ of them have empty intersection. By
the Lemma 5.6, it contradicts ccc. ∎

######  Lemma 5.6.

Suppose $\mathcal{A}$ is a family of open subsets of a space $X$,
$|\mathcal{A}|=\kappa$ and the intersection of any $n$ sets from the family is
empty. Then there are $\kappa$-many pairwise disjoint open subsets of $X$.

###### Proof.

Let $\mathcal{A}=\\{A_{\alpha}\colon\ \alpha<\kappa\\}$ and define

$\mathcal{A}_{l}=\\{A_{0}\cap\dots\cap A_{l-1}\neq\emptyset\colon\
A_{j}\in\mathcal{A},\ j<l\\}.$

Find $m<n$ such that $|\mathcal{A}_{m}|=\kappa$, and
$|\mathcal{A}_{m+1}|=\xi<\kappa$. Let

$J=\\{\alpha<\kappa:\ \exists\alpha_{1}\dots\alpha_{m}\ (A_{\alpha}\cap
A_{\alpha_{1}}\cap\dots\cap A_{\alpha_{m}})\in\mathcal{A}_{m+1}\\}$

and let $I=\kappa\setminus J$. Then $|J|\leq|\xi\cdot(m+1)|=\xi$. Let

$\mathcal{C}=\\{U\in\mathcal{A}_{m}:\ \exists\beta\in I\
\exists\alpha_{1},\dots\alpha_{m-1}\ U=(A_{\beta}\cap
A_{\alpha_{1}}\cap\dots\cap A_{\alpha_{m-1}})\\}.$

Notice that since $|J^{m}|=\xi$, we have $|\mathcal{C}|=\kappa$. As $J\cap
I=\emptyset$, $\mathcal{C}$ is a family of pairwise disjoint open sets. ∎

So far, we have the following picture in $\omega^{\ast}$.

avoiding atomless measuresavoiding p. atomic measures
${\mbox{(}\mu\mbox{-point)}}$(weak P-point)avoiding
measures${\mathfrak{c}\mbox{-OK-point}}$ P-point

We will now study the relation between weak P-points and $\mu$-points.

######  Theorem 5.7.

There is a weak $P$-point which is not $\mu$-point.

###### Proof.

By [20] if $\mathcal{B}$ is a complete Boolean algebra of cardinality
$\mathfrak{c}$, then $St(\mathcal{B})$ can be embedded as a $\mathfrak{c}$-OK
subset of $\omega^{\ast}$. Therefore, we can embed the Stone space $Y$ of the
measure algebra into $\omega^{\ast}$ as an $\mathfrak{c}$-OK set. By Theorem
4.7 there is a weak P-point in the Stone space of the measure algebra. Then
$Y$ contains a weak P-point $p$ (relatively to $Y$). Hence, as $Y$ is a weak
P-set, $p$ is a weak P-point in $\omega^{\ast}$. There is the canonical
(Lebesgue) non-atomic measure $\lambda$ on $Y$ with
$supp(\lambda)=\overline{Y}$. Hence $p\in supp(\lambda)$ and so it is not a
$\mu$-point. ∎

Now, we will come back to Remark 4.9. Let $x$ be a $\mathfrak{c}$-OK point in
$\beta\omega$. Then, $x$ is a $\mu$-point, but $x$ is not a weak P-point
(because of Proposition 4.6). We will use this result to show that there is a
$\mu$-point which is not a weak $P$-point in $\omega^{\ast}$.

######  Theorem 5.8.

There is $\mu$-point in $\omega^{\ast}$ which is not a weak $P$-point.

###### Proof.

Since $\mathcal{P}(\omega)$ is a complete Boolean algebra, by [20],
$\beta\omega$ can be embedded as a $\mathfrak{c}$-OK subset of
$\omega^{\ast}$. Denote this copy by $K$. Let $x\in K$ be a $\mathfrak{c}$-OK
point (relatively to $K$). The point $x$ is not a weak P-point (as it is in
the closure of the copy of $\omega$ in $K$). We will show that it avoids non-
atomic measures.

Let $\mu$ be a non-atomic measure and let $L$ be its support. Then $L\setminus
K$ is ccc. Therefore, $\overline{L\setminus K}\cap K=\emptyset$ as $K$ is a
$\mathfrak{c}$-OK set. So, we may assume without loss of generality, that
$\mu$ is supported by $K$ (considering $\mu_{|K}$ instead of $\mu$, if
needed). But then $x$ is $\mathfrak{c}$-OK point in $K$ and so
$x\notin\mathrm{supp}(\mu)$. ∎

##  6\. Ultrafilters avoiding measures and measure zero ultrafilters

The space $\omega^{\ast}$ is very far from supporting a strictly positive
measures (e.g. as it contains an antichain of open sets of size
$\mathfrak{c}$). However, as we have learned in Proposition 4.1, this is not
enough to deduce that it contains a $\mu$-point. We may try to construct
$\mu$-point in $\omega^{\ast}$ by transfinite induction but we immediately
face the following problem: there are too many non-atomic measures to ’kill’
them inductively one by one.

Fortunately, we are able to ’kill’ many measures at the same time and in fact
we will not ’kill’ measures but rather trees of subsets of $\omega$. With
every non-atomic measure we can associate a tree $T$ witnessing its non-
atomicity. Adding a set appropriate for this tree will ensure that the
resulting ultrafilter will avoid all the measures for which $T$ is a non-
atomicity witness.

We will present the details of this idea. Then, we show its connection to
measure zero ultrafilters (in the sense of Baumgartner) and the constraints of
this method.

So, we will start with several definitions concerning trees.

A family $\mathcal{T}$ is a _tree of subsets of_ $\omega$ if
$\mathcal{T}=\\{T_{s}\colon s\in 2^{<\omega},\ T_{s}\subseteq\omega\\}$ where

  * •

if $s,t\in 2^{<\omega}$, and $s$ extends $t$, then,
$T_{s}\subseteq^{\ast}T_{t}$,

  * •

$\bigcup\\{T_{s}\colon s\in 2^{k}\\}=^{\ast}\omega$ and $T_{s}\cap
T_{t}=^{\ast}\emptyset$ for each $s,t\in 2^{k}$ for every level $k\in\omega$
(notice that we allow $T_{s}$ to be empty).

A tree $T$ is called _a full tree_ if for every $s\in 2^{<\omega}$ the set
$T_{s}$ is infinite. For a set $X\subseteq\omega$ and a tree $\mathcal{T}$ of
subsets of $\omega$ let

$T_{X}=\\{x\in 2^{\omega}\colon\forall k\ |T_{x|k}\cap X|=\omega\\}.$

Fix an ideal $\mathcal{I}$ on $2^{\omega}$. We say that a set $X$
_$\mathcal{I}$ -diagonalizes_ a tree $\mathcal{T}$ (of subsets of $\omega$) if
$T_{X}\in\mathcal{I}$. An ultrafilter $\mathcal{I}$-diagonalizes a tree
$\mathcal{T}$ if it contains an element $\mathcal{I}$-diagonalizing
$\mathcal{T}$. Finally, we say that an ultrafilter _$\mathcal{I}$
-diagonalizes the trees_ if it $\mathcal{I}$-diagonalize every tree of subsets
of $\omega$.

######  Remark 6.1.

The property of $\mathcal{I}$-diagonalizing trees can be stated in the
topological terms, using the Stone duality. Namely, an ultrafilter
$\mathcal{U}$ $\mathcal{I}$-diagonalize (full) trees if and only if for each
continuous (surjective) function $f\colon\omega^{\ast}\to 2^{\omega}$, there
is a clopen $C\subseteq\omega^{\ast}$ such that $f[C]\in\mathcal{I}$.

######  Example 6.2.

Suppose $\mathcal{U}$ is a P-point in $\omega^{\ast}$. Let $Fin$ denote the
ideal of finite subsets of $\omega$. Then $\mathcal{U}$ $Fin$-diagonalizes
every tree of subsets of $\omega$. Indeed, every tree of subsets of $\omega$
has a branch of elements of $\mathcal{U}$. Let $X\in\mathcal{U}$ be a pseudo-
intersection of this branch, promised by P-pointness. Then $|T_{X}|=1$.

So, the property of $\mathcal{I}$-diagonalizing trees, can be seen as a
generalization of the P-point property. We will first prove how the
ultrafilters which $\mathcal{N}$-diagonalize trees of subsets of $\omega$ can
be used to construct $\mu$-points. Then, we will see that the notion of
ultrafilters $\mathcal{I}$-diagonalizing trees is in fact the well-known
notion of $\mathcal{I}$-ultrafilters in disguise.

By _the Cantor algebra_ $\mathbb{C}$ we mean the unique, up to isomorphism,
countable atomless Boolean algebra. We will identify $\mathbb{C}$ with the
$Clop(2^{\omega})$, the Boolean algebra of clopen subsets of $2^{\omega}$.
Notice that $\mathrm{St}(\mathbb{C})=2^{\omega}$.

######  Lemma 6.3.

Let $\mu$ be a measure on the Cantor algebra $\mathbb{C}$. For every
$k\in\omega$ and for each $\varepsilon>0$, there is a partition
$\\{S_{1},\dots,S_{k}\\}$ of unity of $\mathbb{C}$, such that

$\forall i\leq k\ \ \ |\mu(S_{i})-\frac{1}{k}|<\varepsilon.$

###### Proof.

Choose any $\delta>0$ such that

$\delta<\min(\frac{1}{k},\frac{\varepsilon}{k-1}).$

By non-atomicity of $\mu$, pick any partition $\\{P_{1},\dots P_{r}\\}$ of
unity of $\mathbb{C}$ into sets of measure smaller than $\delta$. Let
$a_{i}=\mu(P_{i})$ for $i\leq r$. We are going to construct $S_{i}$’s for
$i<k$ by induction, constructing simultaneously a sequence $(n_{i})$ of
integers. Let $n_{1}=1$. For $i<k$ let

$n_{i+1}=\max\\{m\colon\sum_{j=n_{i}}^{m}a_{i}\leq\frac{1}{k}\\}+1$

and let

$S_{i}=\bigcup\limits_{j\in[n_{i},n_{i+1})}P_{j}.$

By maximality of $n_{i}$’s we have $0<1/k-\mu(S_{i})\leq\delta<\varepsilon$
for each $i<k$. Define $S_{k}=\omega\setminus\bigcup_{i<k}S_{i}$. Then

$\displaystyle\mu(S_{k})=k\cdot\frac{1}{k}-\sum_{i=1}^{i<k}\mu(S_{i})=\frac{1}{k}+\sum_{i=1}^{i<k}\left(\frac{1}{k}-\mu(S_{i})\right)\leq\frac{1}{k}+(k-1)\delta\leq\frac{1}{k}+\varepsilon,$

and so

$|\mu(S_{k})-1/k|<\varepsilon.$

∎

In what follows by $\lambda$ we will mean the Lebesgue measure on
$2^{\omega}$.

######  Theorem 6.4.

For every non-atomic measure $\mu$ on $2^{\omega}$, there exists a surjective
function $f\colon 2^{\omega}\to 2^{\omega}$, such that whenever $S\subseteq
2^{\omega}$ is closed and $\lambda(S)=0$, then $\mu(f^{-1}(S))=0$.

###### Proof.

For every sequence $\\{\varepsilon_{i}\colon\ \varepsilon_{i}>0,\
i\in\omega\\}$, it is possible to construct an embedding
$i\colon\mathbb{C}\to\mathbb{C}$, such that for every level $k$ and every node
$v\in 2^{k}$ we have

$\max(\mu(i(v^{\frown}0)),\mu(i(v^{\frown}1)))\leq\frac{1}{2}\mu(i(v))+\varepsilon_{k+1}.$

We will construct $i$ by induction. Suppose that $i(u)$ is defined for all
nodes $u\in 2^{\leq k}$. For $v\in 2^{k}$ consider the Boolean algebra
$\mathbb{C}\restriction i(v)$ and the restriction of $\mu$ respectively. Since
the restriction of a non-atomic measure on an element of positive measure is
non-atomic, using Lemma 6.3 we can divide $i(v)$ into 2 sets with the
’precision’

$\varepsilon=\frac{\varepsilon_{k+1}}{\mu(i(v))}$

to define $i(v^{\frown}0),i(v^{\frown}1)$ as desired. Continue for all nodes
$v\in 2^{k}$ and all the levels $k$. The function $i\colon
2^{<\omega}\to\mathbb{C}$ can be extended to the desired embedding.

Now, let $\varepsilon_{k}=2^{-2k}$ for every $k\in\omega$. Let
$f_{k},g_{k}\colon\mathbb{R}\to\mathbb{R}$ be defined by
$f_{k}(x)=\frac{1}{2}x+\varepsilon_{k}$, and $g_{k}=(f_{k}\circ\dots\circ
f_{1})$. Then

$g_{k}(1)=2^{-k}+\varepsilon_{1}2^{-k+1}+\dots+\varepsilon_{k}=2^{-k}+2^{-k}\sum_{i=1}^{k}2^{i}\varepsilon_{i}=2^{-k}+2^{-k}\sum_{i=1}^{k}2^{-i}<2\cdot
2^{-k}.$

Notice, that if $i$ is constructed as above, then for every $v\in 2^{k}$ we
have $\mu(i(v))\leq g_{k}(1)<2\cdot\lambda([v])$ (where $[v]$ is the clopen
subset of $2^{\omega}$ generated by $v$). Suppose that $S$ is a closed
subspace of $2^{\omega}$ such that $\lambda(S)=0$. Since $S$ is compact, and
$\lambda$ is outer regular with respect to open sets, given $\delta>0$ we can
find a clopen $U$, such that $S\subseteq U$, $\lambda(U)\leq\frac{\delta}{2}$,
and without loss of generality $U=\bigcup_{j\leq n}[v_{j}]$ for some $n,\ k$
and $v_{j}\in 2^{k}$.

Let $f\colon 2^{\omega}\to 2^{\omega}$ be the continuous map dual to the
embedding $i$, i.e. $f(y)=\bigcap\\{[i(C)]\colon y\in[C]\\}$.

Then

$\mu({f}^{-1}(S))\leq\mu({f}^{-1}[U])=\mu(i(U))=\sum_{j\leq
n}\mu(i(s_{j}))\leq 2\cdot\sum_{j\leq n}\nu(s_{j})=2\cdot\nu(U)<\delta$

As $\delta$ was arbitrary, $f$ is as desired. ∎

######  Corollary 6.5.

For every non-atomic measure $\mu$ on $\beta\omega$, there is a tree
$\mathcal{T}$ such that for every $U\subseteq\omega$ satisfying
$T_{U}\in\mathcal{N}$ we have $\mu[U]=0$. Consequently, if an ultrafilter
$\mathcal{N}$-diagonalizes full trees, then it avoids non-atomic measures.

###### Proof.

By non-atomicity of $\mu$ we can construct a surjective function
$f\colon\beta\omega\to 2^{\omega}$ such that the image measure
$\nu(\cdot)=\mu(g^{-1}(\cdot))$ is non-atomic on $2^{\omega}$.

By Theorem 6.4 we can find a surjective function $g\colon 2^{\omega}\to
2^{\omega}$ such that for every closed $S\subseteq 2^{\omega}$ if
$\lambda(S)=0$, then $\nu(g^{-1}(S))=0$. Let $\mathcal{T}$ be the tree of
subsets of $\omega$ induced in a natural way by the tree $\\{(g\circ
f)^{-1}[v]\colon v\in 2^{<\omega}\\}$ (of subsets of $\beta\omega$). Then, by
surjectivity of the functions $f$ and $g$, the tree $\mathcal{T}$ is full.
Also, $T_{U}=(g\circ f)[U]$ for each $U\subseteq\omega$ (here we treat $U$
once as a subset of $\omega$ and once as a clopen subset of $\beta\omega$).

Therefore, given that $\lambda(g\circ f[U])=0$ for some $U\subseteq\omega$, we
have

$\mu([U])\leq\mu(f^{-1}(f[U]))=\nu(f[U])\leq\nu(g^{-1}(g(f[U])))=0.$

∎

Using the above fact one can construct in a standard way, by a transfinite
induction, a $\mu$-point which is not a P-point (at least under $CH$). It is
enough to make sure to $\mathcal{N}$-diagonalize every tree of subsets of
$\omega$. Instead of performing the construction, we will show that
ultrafilters $\mathcal{I}$-diagonalizing trees are in fact well known
$\mathcal{I}$-ultrafilters, in the sense of Baumgartner. If $\mathcal{I}$ is
the ideal of null sets, such ultrafilters are called measure zero
ultrafilters.

######  Definition 6.6.

Let $\mathcal{I}$ be an ideal on $2^{\omega}$ (containing singletons). We say
than an ultrafilter $\mathcal{U}$ is an $\mathcal{I}$-ultrafilter if for every
function $f\colon\omega\to 2^{\omega}$ there is $X\in\mathcal{U}$ such that
$\overline{f[X]}\in\mathcal{I}$.

######  Proposition 6.7.

Suppose $\mathcal{I}$ is a $\sigma$-ideal on $2^{\omega}$. An ultrafilter
$\mathcal{U}$ $\mathcal{I}$-diagonalizes trees if and only if it is an
$\mathcal{I}$-ultrafilter.

###### Proof.

($\implies$) Consider a function $f\colon\omega\to 2^{\omega}$. By Remark 6.1
we can find $V\subseteq\omega$, such that for $C=[V]\cap\omega^{\ast}$ we have
that $\beta f(C)\in\mathcal{I}$ . Then $\overline{f(V)}=\beta f([V])=\beta
f(C)\cup\beta f(V)$. Since $V$ is countable, we are done.

($\impliedby$) Given $V\subseteq\omega$, such that
$\overline{f(V)}\in\mathcal{I}$, for $C=[V]\cap\omega^{\ast}$ we have
$\overline{f(V)}=\beta f([V])=\beta f(C)\cup\beta f(V)\supseteq\beta f(C)$. ∎

######  Corollary 6.8.

The ultrafilters $\mathcal{N}$-diagonalizing trees are exactly the measure
zero ultrafilters and so every measure zero ultrafilter is a $\mu$-point.

The measure zero ultrafilters were studied by Baumgartner in [1] and by
Brendle in [4]. Let us mention two relevant results which gives examples of
$\mu$-points which are not P-points.

######  Theorem 6.9.

(Theorem 1.4 in [1]) Under Martin’s Axiom for $\sigma$-centered posets, there
is a measure zero ultrafilter which is not a P-point.

######  Theorem 6.10.

([4]) It is consistent that there are measure zero ultrafilters but there are
no P-points.

However, one cannot hope to prove the existence of $\mu$-points in ZFC using
measure zero ultrafilters:

######  Theorem 6.11.

([25]) Consistently, there are no measure zero ultrafilters.

###### Proof.

Every measure zero ultrafilter is a nowhere dense ultrafilter (i.e.
$\mathcal{I}$-ultrafilter for $\mathcal{I}$ being the ideal of nowhere dense
sets), see [1, Theorem 1.2]. Shelah proved (see [25]) that consistently there
are no nowhere dense ultrafilters. ∎

The last theorem shows that the property of being a measure zero ultrafilter
is significantly stronger than the property of being a $\mu$-point. Anyway,
perhaps the above approach is still worth studying: to prove that an
ultrafilter is a $\mu$-point one does not need to diagonalize all the trees.
E.g. it is natural to care only about full trees. However, as the following
proposition shows this does not give us more general notion.

######  Proposition 6.12.

An ultrafilter $\mathcal{U}$ $\mathcal{\mathcal{N}}$-diagonalizes full trees
if and only if it $\mathcal{\mathcal{N}}$-diagonalizes trees.

###### Proof.

Of course we need to prove only ($\implies$).

Instead of trees we will deal with continuous functions as in Remark 6.1.
Given a continuous function $f\colon\omega^{\ast}\to 2^{\omega}$ let
$Y=f(\omega^{\ast})$. We may assume that $\lambda(Y)=m>0$ and that $Y$ does
not have isolated points (otherwise it is easy to find a clopen set as in
Remark 6.1). Define a measure $\mu$ on $Y$ by

$\mu(S)=\frac{\lambda(S)}{\lambda(Y)}.$

The measure $\mu$ is non-atomic. Indeed, for $\varepsilon>0$ find $n$ such
that $2^{-n}<\varepsilon\cdot m$. Then for a clopen partition $\\{[v]\colon
v\in 2^{n}\\}$ we have

$\mu([v]\cap Y)=\frac{\lambda([v]\cap
Y)}{\lambda(Y)}\leq\frac{\varepsilon\cdot m}{m}=\varepsilon$

By Theorem 6.4 we get a surjective function $g\colon Y\to 2^{\omega}$ such
that for every closed $S\subseteq 2^{\omega}$, if $\lambda(S)=0$, then
$\mu(g^{-1}(S))=0$. Then $g\circ f\colon\omega^{\ast}\to 2^{\omega}$ is
surjective, and using Remark 6.1, we can find a clopen set
$C\subseteq\omega^{\ast}$ such that $\mathcal{U}\in C$ and $\lambda((g\circ
f)(C))=0$. Hence

$\lambda(f(C))\leq\mu(f(C))\leq\mu(g^{-1}(g\circ f(C)))=0.$

∎

Perhaps diagonalizing even more particular family of trees would be enough.
However, we do not have any candidate for such family.

##  7\. $\mu$-points and Q-points

Although it is not related to the main subject of this article, perhaps it is
worth to mention the relationship between $\mu$-points and $Q$-points.

We will show that the property of being a $Q$-point does not imply (at least
consistently) the property of avoiding non-atomic measures. This may be
somehow surprising as elements of a $Q$-point can be arbitrarily ’rare’ as
subsets of $\omega$. So, a $Q$-point cannot extend any density filter (and the
standard non-atomic measures on $\omega^{\ast}$ are exactly extensions of
density filters, see e.g. [3]).

Recall that for an ideal $\mathcal{I}$ on the real line, the covering number
of $\mathcal{I}$, $\mathrm{cov}(\mathcal{I})$, is defined as the smallest
cardinality of a family $\mathcal{A}\subseteq\mathcal{I}$ which covers
$\mathbb{R}$. By $\mathcal{M}$ we denote the $\sigma$-ideal of the meager
subsets of $\mathbb{R}$. The dominating number, $\mathfrak{d}$, is defined as
the smallest cardinality of the family $\mathcal{A}\subseteq\omega^{\omega}$
which is dominating, i.e. such that for every $f\in\omega^{\omega}$ there is
$g\in\mathcal{A}$ such that $g(n)\geq f(n)$ for every $n$.

######  Theorem 7.1.

Consistently, there is a non-atomic measure $\mu$ on $\omega$ and a $Q$-point
$x$ such that $x\in\mathrm{supp}(\mu)$.

###### Proof.

Consider the classical random model, i.e. the model obtained by adding
$\omega_{2}$ random reals to the model of $\mathsf{CH}$.

By [5, Theorem 5.6] in this model there is a filter $\mathcal{F}$ generated by
$\omega_{1}$ sets such that the set

$F=\\{x\in\omega^{\ast}\colon x\mbox{ extends }\mathcal{F}\\}$

supports a measure.

By [6, Theorem 3] if $\mathfrak{d}=\mathrm{cov}(\mathcal{M})$, then every
filter generated by less than $\mathfrak{c}$ many sets can be extended to a
$Q$-point. In the classical random model both $\mathfrak{d}=\omega_{1}$ and
$\mathrm{cov}(\mathcal{M})=\omega_{1}$ (see e.g. [2, Table 4]) and so we can
extend the filter $\mathcal{F}$ to a $Q$-point $x$. Then
$x\in\mathrm{supp}(\mu)$. ∎

##  8\. Open problems

We can play with the definition of measure avoiding points in many ways. E.g.
we can consider some particular properties of measures and ask about the
existence of points avoiding measures with this property. For example, we may
ask about points avoiding measures of countable Maharam type or (in the
context of $\omega^{\ast}$) points avoiding P-measures (also called
(AP)-measures, see [3] or [5]).

In fact we may put this kind of questions in a much more general framework.
Let $X$ be a (compact) topological space and let $(\varphi)$ be a topological
property. We say that a point $x\in X$ _avoids spaces with_ $(\varphi)$ if for
each space $Y\subseteq X$ enjoying $(\varphi)$ and such that $x\notin Y$ we
have $x\notin\overline{Y}$.

In this sense the points avoiding measures are exactly the points avoiding
supports of measures and weak P-points are exactly the points avoiding
separable spaces. One can think that the property of _not_ avoiding spaces
with $(\varphi)$ is some kind of local version of the property $(\varphi)$.
Or, that a point avoiding spaces with $(\varphi)$ is a _single_ witness for
non $(\varphi)$. E.g. if a space has a weak P-point, then it is not only non-
separable but there is a concrete point witnessing its non-separability.

This approach motivates questions of the following form.

######  Problem 8.1.

Let $(\varphi)$ be a topological property. Is it true that whenever a
(compact) space $X$ does not have $(\varphi)$, then it contains a point
avoiding spaces with $(\varphi)$?

Very probably the set of properties for which this is an interesting problem
is very limited. In this article we have considered points avoiding spaces
possessing some chain condition (separability, being a support of a measure,
ccc). Perhaps chain conditions are the first properties to look at in the
context of Problem 8.1.

Distinguishing different chain conditions was a source of many important
problems and results in topology (see e.g. [26]). It is natural to ask about
distinguishing the ’local’ versions of chain conditions. E.g. Theorem 4.7
distinguishes local separability from local support of a measure.

######  Problem 8.2.

Is there a compact space $X$ and $x\in X$ which avoids measures but not ccc
spaces (and, particularly, is not a $\mathfrak{c}$-OK-point)? What about other
chain conditions?

Notice that the standard (consistent) example of a small compact space which
is ccc but is not separable is the Stone space of the Boolean algebra
generated by the Suslin tree. But it is not hard to see that this space does
not contain a point avoiding separable spaces (and so it is a non-separable
space without a point ’witnessing’ its non-separability). So, the examples
distinguishing some chain conditions do not automatically distinguish their
local versions. (However, each ccc compact F-space of weight bigger than
$\mathfrak{c}$ necessarily contains a weak P-point, see [7], so we can
distinguish local version of separability and ccc in ZFC).

Problem 8.2 is connected to the main problem of this article.

######  Problem 8.3.

Is there a ’simple’ ZFC construction of a $\mu$-point?

In Section 6 we tried to attack this problem by ’killing’ trees witnessing
non-atomicity of measures. This approach led us to measure zero ultrafilters,
which consistently may not exist, so perhaps this is a dead-end.

We still hope that there might be some not so complicated measure theoretic
reason that $\omega^{\ast}$ contains $\mu$-points. Mathematicians tried to
show non-homogeneity of $\omega^{\ast}$ using combinatorial and topological
arguments. We found it tempting to try to find an argument of measure
theoretic origin.

## References

  * [1] Baumgartner James E., _Ultrafilters on $\omega$_, J. Symbolic Logic 60(2), 1995, 624–639;
  * [2] Blass Andreas, _Combinatorial cardinal characteristics of the continuum_ , Handbook of set theory. Vols. 1, 2, 3, (2010);
  * [3] Blass Andreas, Frankiewicz Ryszard, Plebanek Grzegorz, Ryll-Nardzewski Czesław, _A note on extensions of asymptotic density_ , Proc. Amer. Math. Soc. 129(11), 2001, 3313–3320;
  * [4] Brendle, Jörg, _Between $P$-points and nowhere dense ultrafilters_, Israel J. Math. 113, 1999, 205–230;
  * [5] Borodulin-Nadzieja Piotr and Sobota Damian, _There is a P-measure in the random model_ , Fund. Math., published online 2023, DOI: 10.4064/fm277-3-2023;
  * [6] Canjar R. Michael, _On the generic existence of special ultrafilters_ , PAMS 110(1), 1990;
  * [7] Dow Alan, _Weak $P$-Points in Compact CCC $F$-Spaces_, Tran. Amer. Math. Soc. Vol. 269, No. 2 (Feb., 1982): 557-565;
  * [8] Dow Alan and van Mill Jan, _Many weak P-sets_ , Topology Appl. 323, 2023, paper no. 108285, 16;
  * [9] Džamonja Mirna and Plebanek Grzegorz, _Strictly Positive Measures on Boolean Algebras_ , The Journal of Symbolic Logic, vol. 73, no. 4, (2008);
  * [10] Fremlin David, _Measure Theory volume 4_ , Torres Fremlin (2003);
  * [11] Frolik Zdenék , _Non-homogeneity of $\beta P-P$._, Commentationes Mathematicae Universitatis Carolinae 008.4 (1967): 705-709;
  * [12] Halmos Paul, _Lectures on Boolean algebras_ , Van Nostrand Reinhold, New York, 1972;
  * [13] Kamburelis Anastasis, _Iterations of Boolean algebras with measure_ , Arch. Math. Logic 29(1), 1989, 21-28;
  * [14] Kunen Kenneth, _Some points in $\beta N$_, Mathematical Proceedings of the Cambridge Philosophical Society, 80(3): 385-398;
  * [15] Kunen Kenneth, _Weak P-points in $N^{\ast}$_, Topology (Proc. Fourth Colloq., Budapest, 1978) , II , North-Holland (1980);
  * [16] Pełczyński Aleksander and Semadeni Zbigniew, _Spaces of continuous functions (III) (Spaces $C(\Omega)$ for $\Omega$ without perfect subsets)_, Studia Mathematica 18.2 (1959): 211-222;
  * [17] Rudin Walter, _Homogeneity problems in the theory of Cech compactifications_ , Duke Math. J. 23 (3) (1956): 409 - 419;
  * [18] Rudin, Walter, _Continuous Functions on Compact Spaces Without Perfect Subsets_ , Proc. Amer. Math. Soc, vol. 8 (1957);
  * [19] Simon Petr, _A countable dense-in-itself dense P-set_ , Topology and Its Applications vol. 123 (2002): 193-198;
  * [20] Simon Petr, _Applications of independent linked families_ , Colloq. Math. Soc. János Bolyai, Vol. 41, (1985);
  * [21] van Douwen Eric, _Finitely additive measures on N_ , Topology and its Applications, Volume 47, Issue 3 (1992): 223-268;
  * [22] van Mill Jan, _An introduction to $\beta\omega$_, Handbook of Set-Theoretic Topology, North-Holland (1984): chapter 11;
  * [23] van Mill Jan, _Weak P-points in Cech-Stone compactifications_ , Trans. Amer. Math. Soc., vol. 273, no 2 (1982), 657–678;
  * [24] Wimmers Edward L., _The shelah P-point independence theorem_ , Israel Journal of Mathematics 43 (1982): 28-48;
  * [25] Shelah, Saharon, _There may be no nowhere dense ultrafilter_ , Logic Colloquium ’95 Haifa, Lecture Notes Logic 11, 1998, 305–324, Springer, Berlin;
  * [26] Todorcevic, Stevo, _Chain-condition methods in topology_ , Topology Appl., 101: 45–82.