Theorem (Erdos 1947) If(份-21-均<1 then it is possible to color the edges of Kn with two colors so that there is no monochromatic Kk subgraph. Let n=2k2]. fork≥3， 21-均<1. There exists a two-coloring without monochromatic Kk. R(k,)>L2k2」
If n k ⇥ · 21 k 2 ⇥ < 1 then it is possible to color the edges of Kn with two colors so that there is no monochromatic Kk subgraph. Theorem (Erdős 1947) for k 3, Let n = 2k/2⇥ . ⌅ n k · 21 ⇥k 2 ⇤ < 1. There exists a two-coloring without monochromatic . Kk R(k,k) > 2k/2⇥
R(k,)>? "3 a 2-coloring of Kn,no monochromatic Kk." The Probabilistic Method: a random 2-coloring of K ∀S∈() event As:S is a monochromatic Kk To prove: 9ped站 Ls∈()」
“∃ a 2-coloring of Kn, no monochromatic Kk.” The Probabilistic Method: a random 2-coloring of Kn ⇥S [n] k ⇥ event AS : S is a monochromatic Kk Pr ⇧ ⇤ ⌥ S( [n] k ) AS ⇥ ⌃ ⌅ > 0 To prove: Dependency! R(k,k) > ?
Lovasz Sieve Bad events:A1,A2,...,An None of the bad events occurs: The probabilistic method:being good is possible
Lovász Sieve • Bad events: • None of the bad events occurs: • The probabilistic method: being good is possible A1, A2,..., An Pr ⇤ n i=1 Ai ⇥ Pr ⇤ n i=1 Ai ⇥ > 0
events:A1,A2,...,An dependency graph:D(V,E) V={1,2,,n} ijEE Ai and Aj are dependent d:max degree of dependency graph A2 A(X1,X4) A4(X4) A3 A2(X1,X2) A5(X3) A3(X2,X3) A5 A4 X1,...,X4 mutually independent
A1 A2 A3 A5 A4 X1,...,X4 mutually independent A1(X1,X4) A2(X1,X2) A3(X2,X3) A4(X4) A5(X3) events: A1, A2, ... , An d : max degree of dependency graph dependency graph: D(V,E) V = { 1, 2, ..., n } ij ∈E Ai and Aj are dependent