The lower bound for 3-majority (Section 4.1) #
From a balanced coloring, where every color has at most n/k + b nodes, no
color can gain much in one round: its count exceeds n/k + (1 + 3/k) b with
probability at most 1/n² (Lemma 4.1, lemma_4_1). The expectation
bound uses ∑ₕ cₕ² ≥ n²/k (Cauchy–Schwarz), and the deviation bound is
Hoeffding's inequality.
Theorem 4.2 (theorem_4_2): following the schedule
b_t = (1 + 3/k)^t b, a union bound over rounds (Dynamics.expList_escape)
and colors shows that as long as b (1 + 3/k)^T ≤ n/k, no color has more than
2n/k nodes after T rounds except with probability k T / n²; in
particular the coloring is not monochromatic when k ≥ 3.
theorem_4_2_log turns the condition into T ≤ (k/3) log (n / (k b)).
Range of k #
Lemma 4.1 needs b ≥ k √(n log n), so the schedule starts at
b ≥ max ((n/k)^{1-ε}, k √(n log n)), and the number of rounds obtained is
(k/3) log (n / (k b)). This is Ω(k log n) when k ≤ n^{1/4 - δ}, but it
degenerates as k approaches (n / log n)^{1/4}, where n/k = k √(n log n).
The paper states the theorem for all k ≤ (n / log n)^{1/4}; see
FORMALIZATION_DIFFERENCES.md.
Lemma 4.1. If color j has at most n/k + b nodes, where
k √(n log n) ≤ b ≤ n/k, then after one round it has at least
n/k + (1 + 3/k) b nodes with probability at most 1/n².
One color stays small. If color j starts with at most n/k + b
nodes, b ≥ k √(n log n) and b (1 + 3/k)^T ≤ n/k, then after T rounds it
has more than n/k + b (1 + 3/k)^T nodes with probability at most T/n².
Theorem 4.2 (lower bound for 3-majority). Let k ≥ 3 and suppose every
color starts with at most n/k + b nodes, where b ≥ k √(n log n). If
b (1 + 3/k)^T ≤ n/k, then the coloring after T rounds is monochromatic with
probability at most k T / n².
Theorem 4.2, logarithmic form. Under the hypotheses of theorem_4_2,
the coloring is still not monochromatic after T ≤ (k/3) log (n / (k b))
rounds, except with probability k T / n². With b = max ((n/k)^{1-ε}, k √(n log n)) and k ≤ n^{1/4-δ}, this is Ω(k log n) rounds.