C1: Distributed Coloring (-2): Revisit Basic Coloring Algorithms

March 07, 2025

• Sperner’s Theorem
• A Simple Coloring Algorithm from Sperner’s Theorem
• From $k$-coloring to $(k-1)$-coloring

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

1. 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)}$.

2. 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.