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:
    1. Randomly color each edge uniformly
    2. 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

TwinMind

Get summaries like this for your own meetings

TwinMind takes notes in the background during meetings, lectures, and calls, then writes the summary for you.

Free plan to get started

No bot joins your calls

Phone, desktop & Chrome apps

Your next meeting, summarized like this

TwinMind listens in the background and turns meetings, lectures, and calls into searchable notes you can chat with. Start free.

Available on phone, desktop & Chrome

Your next meeting, summarized like this

TwinMind listens in the background and turns meetings, lectures, and calls into searchable notes you can chat with. Start free.

Available on phone, desktop & Chrome

Your next meeting, summarized like this

TwinMind listens in the background and turns meetings, lectures, and calls into searchable notes you can chat with. Start free.

Available on phone, desktop & Chrome