2

39

2

$$\newcommand{E}[0]{\mathbb{E}}
\newcommand{G}[0]{\mathbb{G}}
\newcommand{ssm}[0]{\smallsetminus}
$$

We show that $2^\omega$ cannot be partitioned into $\omega$-many parts with the property of Baire, such that any $x\in 2^\omega$ is a universally bounded number of bit flips away from each of the $\omega$-many parts. This shows that the axiom of choice (AC) is necessary for the infinite version of a folklore theorem on error correction.

We will represent a graph $G:(V,E)$ as the symmetrized ordered pairs of its edges. Thus $G\subseteq V^2$ and $(x,y)\in G$ iff $\{x,y\}\in E$. A subset $D\subseteq V$ is a *dominating set* if for any $x\in V\ssm D$, there is some $G$-neighbor $y$ of $x$ with $y\in D$. Such $D$ is a *total dominating set* if moreover the previous condition $x\notin D$ can be removed. A *$k$-part (total) domatic partition* of $V$ is a $k$-part partition of $V$ with each part a (total) dominating set.

In a more colorful language, a $k$-part domatic partition of $V$ is a $k$-coloring of $V$ such that every vertex $x\in V$ sees every possible color in its $G$-neighbors and itself. Similarly, a $k$-part total domatic partition of $V$ is a $k$-coloring of $V$ such that every vertex $x\in V$ sees every possible color in its neighbors.

We shall work in the Polish space $2^\omega$ with the usual topology. We use BP to mean the property of Baire. The equivalence relation $\E_0\subseteq 2^\omega\times 2^\omega$ is defined such that $(x,y)\in\E_0$ iff $x(n)=y(n)$ for cofinitely many $n<\omega$. We will no longer distinguish between $\E_0$ and its induced simple graph $\E_0\ssm\Delta_{2^\omega}$ with $\Delta_{2^\omega}=\{(x,x)\}_{x\in 2^\omega}$.

The folklore theorm on error correction is as follows:

Theorem 1

Given $n<\omega$, the hypercube graph on $2^n$ admits an $n$-part total domatic partition iff $n$ is a power of $2$.

In the sense of the corresponding $n$-coloring, the $n$-regularity of the hypercube graph implies that every vertex sees every color in its neighbors exactly once.

For a two-part video explaining the above theorem, see [2] and [3].

We begin with an easy observation.

Theorem 2

The graph $\E_0$ admits an $\omega$-part closed total domatic partition.

Proof

For $n<\omega$, let $D_n\subseteq 2^\omega$ contain all infinite binary strings of the form $0^{n\frown}1^\frown\ldots$. Thus $\{D_n\}_{n<\omega}$ form a family of $\omega$-many disjoint clopen total dominating sets. The theorem holds as we expand this family into a full partition of $2^\omega$.

This is the highest number of parts we can do, as $\E_0$ is $\omega$-regular.

Typically in the study of graph coloring, one deals with a treeing $\G_0$ of $\E_0$. However as $\G_0$ does not have uniform vertex degree, it makes our analysis more difficult to continue. We shall instead consider the hypercube graph on $2^\omega$, which can be seen as a homogenized version of $\G_0$.

Definition 1

Let $G_1\subseteq 2^\omega\times 2^\omega$ be the graph such that $(x,y)\in G_1$ iff $x$ and $y$ are exactly one bit flip away from each other. This is not a standard definition, and the need to emphasize on the $1$ will come more apparent later.

Theorem 3

For any finite $k<\omega$, the graph $G_1$ admits a $k$-part clopen total domatic partition.

Moreover, under the assumption that “$\E_0$ has a transversal $A\subseteq 2^\omega$”, the graph $G_1$ admits an $\omega$-part total domatic partition.

Proof

The first part of the Theorem is essentially Theorem 1, where we leverage that $2^\omega$ with graph $G_1$ can always be seen as the hypercube graph on $2^n$, but every element carries a tail of junk information.

For the second part, define $\phi:2^\omega\to \omega$, such that for $x\in 2^\omega$, if $x_0$ is the unique element in $A\cap[x]_{\E_0}$, then $\phi(x)$ is the minimal $n<\omega$ such that for all $m\ge n$, $x(m)=x_0(m)$. Next define $\pi:\omega\to\omega$ such that for every $i<\omega$, $\pi^{-1}\{i\}\subseteq\omega$ is infinite.

Note that for every $x\in 2^\omega$ and $m\ge \phi(x)$, if $y$ is the result of flipping the $m$-th bit of $x$, then $(x,y)\in G_1$ and $\phi(y)=m+1$. Thus $x$ has $G_1$-neighbors of all sufficiently large $\phi(y)$. Consequently $x$ has $G_1$-neighbors of every possible $\pi\circ\phi(y)\in\omega$. Letting $D_i=(\pi\circ\phi)^{-1}\{i\}$, we see that $\{D_i\}_{i<\omega}$ is an $\omega$-part total domatic partition of $G_1$.

As a remark, any graph $G$ on $2^\omega$ that contains $G_1$ will share any domatic partition that $G_1$ has, thus such $G$ will always have a finite-part clopen total domatic partition. Finite-part domatic partitions will not continue to be of our main interest, but we'd like to mention without proof that the phenomenon of a finite-part clopen total domatic partition is already present at an intermediate phase between $\G_0$ and $G_1$:

Theorem 4

Let $\sigma:2^{<\omega}\to\omega$ be any function. Let the ($\omega$-regular) graph $G_\sigma$ on $2^\omega$ be defined where $(x,y)\in G_\sigma$ iff there exists a prefix $s\in 2^{<\omega}$ such that $s\subseteq x,y$, and $x$ and $y$ differ for a single bit flip at the location $|s|+\sigma(s)$. Then for any $k<\omega$, the graph $G_\sigma$ admits a $k$-part clopen total domatic partition.

Moreover, $\E_0$ having a transversal implies that $G_\sigma$ will admit an $\omega$-part total domatic partition.

As to the infinte-part domatic partition of $G_1$ from Theorem 3, the chaotic nature of a transversal $A$ of $\E_0$ implies that the partition will have bad descriptive set theoretic properties. In fact there isn't any nice infinite-part domatic partition of $G_1$, as we will see in the next section.

Definition 2

Given $1\le d<\omega$, define the graph $G_d\subseteq 2^\omega\times 2^\omega$ such that $(x,y)\in G_d$ iff $x$ and $y$ are at most $d$-many bit flips away. Thus $G_d$ can be seen as a $\le d$-fold composition of $G_1$ with itself.

We find that the graphs $G_d$ form a hierarchy

$$\G_0\subseteq G_1\subseteq G_2\subseteq G_3\subseteq\ldots\subseteq \E_0$$

with their union $\bigcup_n G_n=\E_0$. This is a process of thinning down the dominating sets of each graph as the graphs $G_d$ become "thicker" with $d$, until $2^\omega$ is big enough to contain $\omega$-many of them. Coincidentally, the partition $\{D_n\}_{n<\omega}$ given in Theorem 2 is such that each $D_n$ is a total dominating set for $G_{n+1}$. In terms of BP dominating sets, this is the best we can do:

Theorem 5

For any $d<\omega$, the graph $G_d$ does not admit any $\omega$-part BP domatic partition.

Proof

We will demonstrate the idea behind the proof using the example of $d=2$, for the fear that the more general case will make notations too cumbersome.

The idea behind the proof is as follows. There is a relatively obvious reason for why $G_d$ does not admit any infinite-part open domatic partition, which is that many vertices will witness the failure of such a domatic partition. In the BP case, there are still enough generic vertices to witness the failure of a domatic partition, in a very similar way.

Let $\{D_k\}_{k<\omega}$ be an $\omega$-part BP domatic partition of $G_2$. For $i\ne j$ finite, let $\gamma_{i,j}$ denote the automorphism of $2^\omega$ by flipping the two bits at locations $i,j$, and similarly define $\gamma_i$ as the automorphism that flips the one bit at $i$. Note that every $D_k$ is non-meager, as $D_k$ and it countably many copies under $\gamma_i$ and $\gamma_{i,j}$ cover all of $2^\omega$.

By localization, assume that $D_0$ is comeager in some basic open $N_s$. Thus any $\gamma_i$ or $\gamma_{i,j}$ with $i,j\ge |s|$ will be an automorphism of $N_s$. The intersection of $D_0$ with its copies under every such $\gamma_i$ and $\gamma_{i,j}$ will remain comeager in $N_s$, with the property that for any $x\in N_s$ in this intersection, any $G_2$-neighbor of the form $\gamma_i(x)$ or $\gamma_{i,j}(x)$ with $i,j\ge |s|$ will remain in $D_0$. Thus anytime this $x$ sees a $G_2$-neighbor that is not in $D_0$, some $<|s|$-th bit of $x$ must be flipped.

This leaves us with $|s|$-many cases. In particular, flipping any one bit of $x$ will make $x$ see at most $|s|$-many new colors, but $x$ will need to see all $\omega$-many colors, so a second bit must be flipped. If we can find some $x$ such that it sees only finitely many new colors even after flipping two bits, then we are done as $x$ is a witness of the failure of the domatic partition.

We will find sequential extensions $(s_n)_{n\le |s|}$ of $s$ as follows. Let $s_0=s$. For every $n<|s|$, consider the basic open set $N_{\gamma_n(s_n)}$. As $\{D_k\}_{k<\omega}$ partitions into it, there is some $k_n<\omega$ such that $D_{k_n}$ is non-meager in $N_{\gamma_n(s_n)}$. By localization, there is some $s_{n+1}\supseteq s_n$ such that $D_{k_n}$ is comeager in $N_{\gamma_n(s_{n+1})}$. By a similar discussion as before, for any generic $x\in N_{\gamma_n(s_{n+1})}$, the $G_1$-neighbors of $x$ will have only finitely many colors. Thus for any generic $x\in N_{s_{n+1}}$, the $G_1$-neighbors of $\gamma_n(x)$ will only have finitely many neighbors.

Thus as $s_{|s|}$ is a common extension of all $s_n$, any $x$ generic in $N_{s_{|s|}}$ will also be generic in every $N_{s_n}$, and we fix such an $x$. Thus for any $n<|s|$, $\gamma_n(x)$ has only finitely many $G_1$-neighbors. Now $\gamma_{i,j}(x)$ takes only one value when $i,j\ge |s|$, and $\gamma_{i,j}(x)$ takes on finitely many values when $i<|s|$ or $j<|s|$. This $x$ has the desired property of having only finitely many $G_2$-neighboring colors, and we arrived at a contradiction.

For the general case of $G_d$, we expect some form of "inductions inside inductions", as we iterate through all cases of how some $x$ gets connected to its $G_d$-neighbors. We still eventually stop after a finite amount of inductions, so the desired result holds.

There are certainly enough combinatoric space to play around with variations of the problem. Here are a few which weaken the notion of boundedness:

Question 1

Let $\{D_n\}_{n<\omega}$ be a BP partition of $2^\omega$, such that for some function $\Phi:\omega\to\omega_{>0}$, every $D_n$ is dominating for the graph $G_{\Phi(n)}$. By Theorem 5 it follows that $\Phi$ is unbounded. Then does there exists some $C>0$, such that for cofinitely many $n<\omega$, it holds that $\Phi(n)\ge C\log n$?

Question 2

For what type of function $\beta:2^\omega\to\omega$, does there exist a BP partition $\{D_n\}_{n<\omega}$ of $2^\omega$, such that every $x\in 2^\omega$ connects to every $D_n$ via a $G_{\beta(x)}$-edge?

Unexpectedly, the case of measure is not as straightforward as BP, due to not having the full localization theorem. Hence we can ask:

Question 3

Do the graphs $G_d$ admit any infinite-part measurable domatic partition, with the usual coin-flipping probability measure on $2^\omega$?

[1]

Alexander S. Kechris, Classical Descriptive Set Theory, Graduate Texts in Mathematics, 65

投稿日：2021年1月29日

更新日：2021年1月29日

投稿者

この記事を高評価した人

高評価したユーザはいません

コメント