AI summary by TwinMind
Lower Bounds to Ramsey Numbers
MIT OpenCourseWare
43m 7s
Introduction to Probabilistic Method and Ramsey Numbers
- Probabilistic method: powerful technique demonstrating existence of combinatorial objects by introducing randomness
- Ramsey number R(k,l): smallest integer n such that any 2-coloring (red/green) of complete graph K_n contains monochromatic K_k or K_l
- Example: R(3,3) = 6
- 6 vertices: always contains monochromatic triangle regardless of coloring
- 5 vertices: possible to color edges avoiding monochromatic triangle
- Ramsey's theorem (1920s): R(k,l) always finite for any k,l
Erdős's Lower Bound (1940s) - Basic Union Bound
- Theorem: R(k,k) > 2^(k/2) for k ≥ 3
- Proof method: Random coloring with union bound
- Color each edge of K_n uniformly at random (red/green with probability 1/2 each)
- For each k-vertex subset S: define bad event A_S = "S induces monochromatic clique"
- P(A_S) = 2 · 2^(-(k choose 2)) = 2^(1-(k choose 2))
- Union bound: P(exists monochromatic k-clique) ≤ (n choose k) · 2^(1-(k choose 2))
- If (n choose k) · 2^(1-(k choose 2)) < 1, then positive probability of no monochromatic k-clique exists
- Refined bound: R(k,k) > (1/e√k/2 + o(1)) · k · 2^(k/2)
- "Needle in haystack" phenomenon: Random coloring works with high probability but hard to verify success
Alteration Method - Improved Lower Bound
- Theorem: R(k,k) > n - (n choose k) · 2^(1-(k choose 2))
- Corollary: R(k,k) > (1/e + o(1)) · k · 2^(k/2) (improvement by factor √k/2)
- Two-step construction:
- Randomly color each edge uniformly
- Delete one vertex from each monochromatic k-clique
- Let X = number of monochromatic k-cliques after step 1
- E[X] = (n choose k) · 2^(1-(k choose 2))
- Delete at most X vertices in step 2
- Final graph has ≥ n - X vertices in expectation
- Therefore exists coloring with ≥ n - E[X] vertices and no monochromatic k-clique
Lovász Local Lemma - Best Known Lower Bound
- Setup: Collection of bad events E_1, ..., E_m with dependencies
- Easy cases:
- Sum of probabilities < 1: apply union bound
- All events independent: probability none occur = ∏(1 - P(E_i))
- Hard case: Events have dependencies
- Random variable model:
- Independent random variables X_1, ..., X_v
- Index sets B_1, ..., B_m ⊆ {1,...,v}
- Event E_i depends only on variables {X_j : j ∈ B_i}
- Hypotheses:
- Each B_i disjoint from at most D other B_j's
- P(E_i) ≤ 1/((D+1)e) for all i
- Conclusion: P(no bad events occur) > 0
Spencer's Result (1970s) - Application of Local Lemma
- Theorem: If (k choose 2) · (n choose 2) · (n-2 choose k-2) · 2^(1-(k choose 2)) < 1/e, then R(k,k) > n
- Corollary: R(k,k) > (√k/2/e + o(1)) · k · 2^(k/2)
- Best known lower bound for diagonal Ramsey numbers to date
- Proof setup:
- Random variables: edge colorings of K_n
- Bad events: k-vertex subsets inducing monochromatic cliques
- B_S corresponds to (k choose 2) edges in clique on vertex set S
- Two k-sets S, S' have overlapping edge sets iff |S ∩ S'| ≥ 2
- Dependency calculation: Each k-set S conflicts with at most (k choose 2) · (n-2 choose k-2) other k-sets
- Apply Local Lemma to conclude positive probability of no monochromatic k-cliques
Summary of Three Approaches
- Union bound: R(k,k) > 2^(k/2)
- Alteration: R(k,k) > (1/e) · k · 2^(k/2)
- Local Lemma: R(k,k) > (√k/2/e) · k · 2^(k/2) (best known)
- Each method introduces progressively more sophisticated probabilistic techniques
