文献あり

Domatic partitions with the property of Baire

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

Definitions

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 ∖ 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^{ω}$ with the usual topology. We use BP to mean the property of Baire. The equivalence relation $E_{0} \subseteq 2^{ω} \times 2^{ω}$ is defined such that $(x, y) \in E_{0}$ iff $x (n) = y (n)$ for cofinitely many $n < ω$ . We will no longer distinguish between $E_{0}$ and its induced simple graph $E_{0} ∖ Δ_{2^{ω}}$ with $Δ_{2^{ω}} = {(x, x)}_{x \in 2^{ω}}$ .

Background

The folklore theorm on error correction is as follows:

Theorem 1

Given $n < ω$ , 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].

The graphs $E_{0}$ , $G_{0}$ and $G_{1}$

We begin with an easy observation.

Theorem 2

The graph $E_{0}$ admits an $ω$ -part closed total domatic partition.

Proof

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

This is the highest number of parts we can do, as $E_{0}$ is $ω$ -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^{ω}$ , which can be seen as a homogenized version of $G_{0}$ .

Definition 1

Let $G_{1} \subseteq 2^{ω} \times 2^{ω}$ 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 < ω$ , 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^{ω}$ ”, the graph $G_{1}$ admits an $ω$ -part total domatic partition.

Proof

The first part of the Theorem is essentially Theorem 1, where we leverage that $2^{ω}$ 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 $ϕ : 2^{ω} \to ω$ , such that for $x \in 2^{ω}$ , if $x_{0}$ is the unique element in $A \cap [x]_{E_{0}}$ , then $ϕ (x)$ is the minimal $n < ω$ such that for all $m \geq n$ , $x (m) = x_{0} (m)$ . Next define $π : ω \to ω$ such that for every $i < ω$ , $π^{- 1} {i} \subseteq ω$ is infinite.

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

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

Moreover, $E_{0}$ having a transversal implies that $G_{σ}$ will admit an $ω$ -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.

The graphs $G_{d}$

Definition 2

Given $1 \leq d < ω$ , define the graph $G_{d} \subseteq 2^{ω} \times 2^{ω}$ 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 $\leq 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 \dots \subseteq E_{0}$
with their union $⋃_{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^{ω}$ is big enough to contain $ω$ -many of them. Coincidentally, the partition ${D_{n}}_{n < ω}$ 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 < ω$ , the graph $G_{d}$ does not admit any $ω$ -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 < ω}$ be an $ω$ -part BP domatic partition of $G_{2}$ . For $i \neq j$ finite, let $γ_{i, j}$ denote the automorphism of $2^{ω}$ by flipping the two bits at locations $i, j$ , and similarly define $γ_{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 $γ_{i}$ and $γ_{i, j}$ cover all of $2^{ω}$ .

By localization, assume that $D_{0}$ is comeager in some basic open $N_{s}$ . Thus any $γ_{i}$ or $γ_{i, j}$ with $i, j \geq | s |$ will be an automorphism of $N_{s}$ . The intersection of $D_{0}$ with its copies under every such $γ_{i}$ and $γ_{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 $γ_{i} (x)$ or $γ_{i, j} (x)$ with $i, j \geq | 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 $ω$ -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 \leq | s |}$ of $s$ as follows. Let $s_{0} = s$ . For every $n < | s |$ , consider the basic open set $N_{γ_{n} (s_{n})}$ . As ${D_{k}}_{k < ω}$ partitions into it, there is some $k_{n} < ω$ such that $D_{k_{n}}$ is non-meager in $N_{γ_{n} (s_{n})}$ . By localization, there is some $s_{n + 1} \supseteq s_{n}$ such that $D_{k_{n}}$ is comeager in $N_{γ_{n} (s_{n + 1})}$ . By a similar discussion as before, for any generic $x \in N_{γ_{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 $γ_{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 |$ , $γ_{n} (x)$ has only finitely many $G_{1}$ -neighbors. Now $γ_{i, j} (x)$ takes only one value when $i, j \geq | s |$ , and $γ_{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.

Future work

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 < ω}$ be a BP partition of $2^{ω}$ , such that for some function $Φ : ω \to ω_{> 0}$ , every $D_{n}$ is dominating for the graph $G_{Φ (n)}$ . By Theorem 5 it follows that $Φ$ is unbounded. Then does there exists some $C > 0$ , such that for cofinitely many $n < ω$ , it holds that $Φ (n) \geq C \log n$ ?

Question 2

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