The Lumenary · First-year graduate

The probabilistic method

Name: ______________________

Date: ______________________

You will learn to

Prove Erdős's bound $R(k, k) > 2^{k/2}$ for $k \geq 3$ with a random colouring, and improve it by the deletion method
Use linearity of expectation and alteration arguments to prove existence results, including graphs of large girth and large chromatic number
Use the second-moment method to find a threshold in random graphs
Prove the Lovász local lemma and the Chernoff bound, and apply them to satisfiability, colourings and discrepancy
Distinguish existence proofs from explicit constructions, and derandomise where possible (conditional expectations, Moser–Tardos)

1.
Colour the edges of $K_6$ red or blue by independent fair coin flips. What is the expected number of monochromatic triangles?
2.
For a random colouring of $K_6$ , the expected number $X$ of monochromatic $K_4$ 's is $\binom 64 2^{1-6} = \frac{15}{32} \approx 0.47$ . What can we conclude?
- A.At least $53\%$ of colourings have no monochromatic $K_4$ ; in particular $R(4,4) > 6$ .
- B.No colouring of $K_6$ has a monochromatic $K_4$ .
- C.Exactly $47\%$ of colourings have a monochromatic $K_4$ .
- D.Nothing, because the events for different $4$ -sets are dependent.
3.
What is the largest $n$ for which the first-moment condition $\binom n4 \, 2^{1 - \binom 42} < 1$ holds? (It proves $R(4, 4) > n$ .)
4.
In the proof that every graph with $m$ edges has a cut of size $\ge m/2$ , we write $X = \sum_e X_e$ with $X_e = 1$ if edge $e$ is cut, and conclude $\mathbb{E}[X] = m/2$ . The $X_e$ are not mutually independent (the three edges of a triangle cannot all be cut). Why is the conclusion still valid?
- A.Linearity of expectation holds for any random variables, independent or not.
- B.Because the $X_e$ are pairwise independent, which is enough for linearity.
- C.Because we may assume the graph has no triangles.
- D.It is not valid; a different proof is needed for graphs with triangles.
5.
In Erdős's proof of Theorem 3, with $p = n^{\theta - 1}$ and $\theta < 1/g$ , why do we delete a vertex from each short cycle instead of asking that the random graph have no short cycles at all?
- A.The expected number of short cycles, about $\sum_{i \le g}(np)^i/(2i)$ , tends to infinity, so the random graph almost surely has some; but it is $o(n)$ , so deleting them costs few vertices.
- B.Deleting vertices increases the chromatic number.
- C.We could take $p$ smaller so that there are no short cycles, but deletion is just shorter to write.
- D.Because girth is only defined for graphs that have cycles.
6.
In a $10$ -CNF formula (every clause has $10$ literals on distinct variables), each clause shares variables with at most $d$ other clauses. What is the largest $d$ for which the symmetric Lovász local lemma ( $e\,p\,(d+1) \le 1$ ) guarantees that the formula is satisfiable?
7.
Let $S$ be a sum of $n = 10000$ independent random signs $\pm 1$ . Which is the Chernoff bound (Theorem 6) for $\mathbb{P}(S \ge 400)$ ?
- A. $e^{-8} \approx 3.4 \times 10^{-4}$
- B. $1/16 = 0.0625$
- C. $e^{-4} \approx 0.018$
- D. $0$ , because $400 > 4\sqrt n$ is impossible.
8.
With Colouring n the red/blue colourings of the edges of $K_n$ and Monochromatic c K meaning that all edges inside the vertex set K have the same colour under c, which Lean statement says $R(k, k) > n$ ?
- A.∃ c : Colouring n, ∀ K : Finset (Fin n), K.card = k → ¬ Monochromatic c K
- B.∀ c : Colouring n, ∃ K : Finset (Fin n), K.card = k ∧ Monochromatic c K
- C.∃ c : Colouring n, ∃ K : Finset (Fin n), K.card = k ∧ ¬ Monochromatic c K
- D.∀ c : Colouring n, ∀ K : Finset (Fin n), K.card = k → ¬ Monochromatic c K
9.
Write expected_mono(n, k) returning $\binom nk 2^{1 - \binom k2}$ as an exact Fraction, and first_moment_bound(k) returning the largest $n \ge k$ with expected_mono(n, k) < 1 (so that $R(k, k) > n$ ).
Computational — Practice

Answer key — The probabilistic method

1.
By linearity, $\mathbb{E}[X] = \binom 63 \cdot 2^{1 - \binom 32} = 20 \cdot \frac14 = 5$ . (Since every colouring of $K_6$ has at least one monochromatic triangle — indeed at least two, by Goodman's formula — this is consistent with $R(3,3) = 6$ .)
2.
Since $X$ takes non-negative integer values, $\mathbb{P}(X \ge 1) \le \mathbb{E}[X] = 15/32$ , so $\mathbb{P}(X = 0) \ge 17/32 \approx 0.53$ . Hence some (indeed more than half of all) colourings of $K_6$ have no monochromatic $K_4$ , and $R(4, 4) > 6$ . The first experiment estimates $\mathbb{P}(X = 0) \approx 0.69$ .
3.
The condition is $\binom n4 < 32$ . Since $\binom 64 = 15 < 32 \le \binom 74 = 35$ , the largest $n$ is $6$ : the first moment proves $R(4, 4) > 6$ , while the truth is $R(4, 4) = 18$ . For small $k$ explicit constructions win; for large $k$ the random bound is the best known.
4.
On a finite probability space, $\mathbb{E}[\sum_e X_e] = \sum_\omega \mathbb{P}(\omega)\sum_e X_e(\omega) = \sum_e \sum_\omega \mathbb{P}(\omega)X_e(\omega) = \sum_e \mathbb{E}[X_e]$ — just exchanging two finite sums. Each edge is cut with probability $1/2$ , so $\mathbb{E}[X] = m/2$ , and some cut has $X \ge m/2$ . Independence would matter if we wanted the distribution of $X$ or its variance.
5.
$\mathbb{E}[Y] \approx \sum_{i=3}^{g}\frac{n^{\theta i}}{2i}$ , which tends to infinity (so $Y = 0$ is unlikely) but is $o(n)$ because $\theta g < 1$ . By Markov, $Y < n/2$ with high probability, and deleting one vertex per short cycle keeps more than half of the vertices while destroying all short cycles. Requiring $Y = 0$ outright would force $np \to 0$ , and then $\alpha(G)$ would be too large for the chromatic number bound.
6.
Each clause fails with probability $p = 2^{-10} = 1/1024$ , and the events for two clauses are mutually independent of all clauses sharing no variables with them. The condition $e\,p\,(d+1) \le 1$ is $d + 1 \le 1024/e \approx 376.7$ , so $d \le 375$ . Then the formula is satisfiable however many clauses it has — and Moser–Tardos finds a satisfying assignment quickly.
7.
$a^2/(2n) = 160000/20000 = 8$ , so $\mathbb{P}(S \ge 400) < e^{-8} \approx 3.4 \times 10^{-4}$ . Chebyshev gives only $\operatorname{Var}S/a^2 = 1/16$ . (The true value is close to the normal tail $\mathbb{P}(Z \ge 4) \approx 3.2 \times 10^{-5}$ .)
8.
$R(k, k)$ is the least $n$ such that every colouring has a monochromatic $K_k$ . So $R(k, k) > n$ means some colouring of $K_n$ has no monochromatic $K_k$ : ∃ c, ∀ K, K.card = k → ¬ Monochromatic c K. The lesson's Lean theorem proves exactly this for $k \ge 3$ and $n^2 \le 2^k$ .
9.
```
from fractions import Fraction
from math import comb

def expected_mono(n, k):
    return Fraction(2 * comb(n, k), 2 ** comb(k, 2))

def first_moment_bound(k):
    n = k
    while expected_mono(n + 1, k) < 1:
        n += 1
    return n
```
The starter forgot the factor $2$ for the two colours and so claimed $R(4,4) > 7$ , which the first-moment method does not prove. With the correct expectation, $R(4,4) > 6$ , $R(5,5) > 11$ and $R(10,10) > 100$ — compare Theorem 1's closed form $2^{k/2}$ , which gives $4$ , $5$ and $32$ , and the known values $R(4,4) = 18$ and $43 \le R(5,5) \le 46$ .