Reminder: This post contains 3031 words
· 9 min read
· by Xianbin
This post revisited previous basic coloring algorithm in LOCAL model.
Sperner’s Theorem
Let \(S\) denote a set of \(n\) objects.
\(\textbf{Theorem}\). Given a Sperner collection \(C\) on \(S\) (each set will not be the subset of another one), we have
\(\sum_{A\in C} \frac{1}{n \choose k} \leq 1\)
where \(\lvert A \rvert = k\).
The above theorem means that \(\sum_{A\in C} \leq { n \choose k} \leq {n \choose \lfloor n/2 \rfloor}\).
Formal Proof (by ChatGPT).
Consider all \(n!\) maximal chains in the subset lattice \(P([n])\), each containing exactly one subset of every size. Each maximal chain is of the form: \(\emptyset \subset \{x_1\} \subset \{x_1, x_2\} \subset \dots \subset \{x_1, x_2, \dots, x_n\} = [n]\). Each chain has exactly one set of size \(k\) where \(k\in [n]\).
For an antichain \(C\), the fraction of chains passing through any \(A \in C\) is \(\frac{1}{\binom{n}{\lvert A\rvert}}\) , summing (the expected number of times a random maximal chain intersects \(C\)) to at most 1 (each set \(A\) in \(C\) has one contribution; all together, they contributed at most 100%):
\[\sum_{A\in C} \frac{1}{\binom{n}{|A|}} \leq 1.\]
Maximizing \(\lvert C\rvert\) occurs when \(C\) consists of subsets of size \(\lfloor n/2 \rfloor\), yielding
\[\lvert C \vert \leq \binom{n}{\lfloor n/2 \rfloor}.\]
By [1].
For each \(A\subset S\), there are exactly \(\lvert A \rvert ! (n - \lvert A \rvert)!\) maximal chains of \(S\). Since of none of the \(n!\) maximal chains of \(S\) meets \(C\) more than one time, we have
\[\sum_{A\in S} \lvert A \rvert ! (n - \lvert A \vert )! \leq n!\]
(Two different ways of counting!)
A Simple Coloring Algorithm from Sperner’s Theorem
By Sperner’s theorem, we can see that it is easy to construct a set of subsets such that each subset does not belong to another one. It is extremely helpful in coloring.
\(\textbf{Lemma 1}\). Given a \(k\)-coloring \(c_1\) of a root tree, there exists an algorithm such that in a single round we can compute a \(k' = \log k + \log\log k /2 + 1\) without communication.
\(\textbf{Proof}\). The idea is simple. For a root tree, each node will know who is its parent. The main idea is to map \(\{1, \ldots, k\}\) to a set \(S_{k'}\) of subset. Now, let us imagine that if \(\lvert S_{k'} \rvert\) is at least \(k\), then it means that we have a one-to-one mapping. Since our goal is to find a correct coloring, we do not allow that \(C_i \subseteq C_j \in S_{k'}\) (sufficient condition). (In a tree, to have a correct coloring, it is enough to consider these nodes \(a_1 \rightarrow a_2\). Since it is one-to-one mapping, each color will be map to a distinct map. Also, for any \(C_i \cap C_j \neq \emptyset\). We can always select a new for \(a_2\). Then it is done.
After apply Lemma1 for \(\log ^* n\) times, we obtain a \(O(1)\)-coloring.
Next, let us see how to obtain a 3-coloring.
From \(k\)-coloring to \((k-1)\)-coloring
-
Each node \(u\) sends its color \(color(u)\) to its children. Each node \(v\) use his parent color, i.e., \(color(u)\). (Notice that at this moment, all children have the same color). For the root node, we arbitrarily select one from \(\{1, 2, 3\} \setminus {color(r)}\).
-
If the current color of \(v\) is less than \(k\), we keep the color. Otherwise, we select any color from \(\{1,2,3\}\setminus \{color(w), color(v)\}\). (\(w\to u\to v\)).
The observation is that nodes \(u\) with color \(k\) build an independent set. So, it is a proper coloring.
After applying the above procedure for constant times, we obtain a 3-coloring.
[1]. Lubell, D., 1966. A short proof of Sperner’s lemma. Journal of Combinatorial Theory, 1(2), p.299.