南京大学：《组合数学 Combinatorics》课程教学资源（课件讲稿）Ramsey Theory-2

Ramsey Theorem

Ramsey Theorem

R(k,)A the smallest integer satisfying: if n=R(k,D),for any 2-coloring of Kn, there exists a red Kk or a blue Ki. 2-coloring of Kn f:(）--od.blwo} Ramsey Theorem R(kl)is finite. Frank P.Ramsey (1903-1930) R(3,3)=6

R(k,l) the smallest integer satisfying: ￾ Ramsey Theorem R(k,l) is finite. 2-coloring of Kn f : ￾[n] 2 ⇥ ￾ {red, blue} if n≥ R(k,l), for any 2-coloring of Kn, there exists a red Kk or a blue Kl. R(3,3) = 6 Frank P. Ramsey (1903-1930)

If n=Ri(r;k1,k2,...kr), r-colering:(）h ie{1,2,...,r}and Sc[n withS= such that entire is colored by i Theorem(Ramsey 1930) Ri(r;k1,k2,...,kr)is finite

If n ≥ Rt(r; k1, k2, ... , kr), Theorem (Ramsey 1930) Rt(r; k1, k2, ... , kr) is finite. ∀ r-coloring ∃i∈{1,2,...,r} and S⊆[n] with |S|=ki such that entire f : ￾[n] t ￾ ￾ [r] ￾S t ￾ is colored by i

Ifn≥R(r;k≌t(r;k,,) rin:()→月 ョa monochromatic with S[n]and | Theorem(Ramsey 1930) Ri(r;k)is finite

If n ≥ Rt(r; k) Theorem (Ramsey 1930) Rt(r; k) is finite. ∀ r-coloring ∃ a monochromatic with S⊆[n] and |S|=k f : ￾[n] t ￾ ￾ [r] ￾S t ￾ ￾ Rt(r; k,..., k ￾ ￾￾ ￾ r )

Ramsey Theorem Applications

Ramsey Theorem Applications

Happy Ending Problem Any 5 points in the plane,no three on a line,has a subset of 4 points that form a convex quadrilateral

Happy Ending Problem Any 5 points in the plane, no three on a line, has a subset of 4 points that form a convex quadrilateral

Theorem (Erdos-Szekeres 1935) Vm≥3，N(m)such that any set of n≥W(m) points in the plane,no three on a line,contains m points that are the vertices of a convex m-gon. Polygon: convex concave

Polygon: convex concave ∀ m ≥ 3, ∃ N(m) such that any set of n ≥ N(m) points in the plane, no three on a line, contains m points that are the vertices of a convex m-gon. ∀ m ≥ 3, ∃ N(m) such that any set of n ≥ N(m) points in the plane, no three on a line, contains m points that are the vertices of a convex m-gon. Theorem (Erdős-Szekeres 1935)

Theorem (Erdos-Szekeres 1935) Vm≥3，N(m)such that any set of n≥N(m) points in the plane,no three on a line,contains m points that are the vertices of a convex m-gon. Polygon: convex concave

Polygon: convex concave ∀ m ≥ 3, ∃ N(m) such that any set of n ≥ N(m) points in the plane, no three on a line, contains m points that are the vertices of a convex m-gon. ∀ m ≥ 3, ∃ N(m) such that any set of n ≥ N(m) points in the plane, no three on a line, contains m points that are the vertices of a convex m-gon. Theorem (Erdős-Szekeres 1935)

Theorem (Erdos-Szekeres 1935) Vm≥3，N(m)such that any set of n≥W(m) points in the plane,no three on a line,contains m points that are the vertices of a convex m-gon. W(m)=R3(2;m,m) XI R3(2;m,m) f:(3)→{0,1} 3ScX,S m monochromatic (3) X:set of points in the plane,no 3 on a line Va,b,c∈X,△abc:points in triangle abc f({a,b,c})=Aabe mod 2

∀ m ≥ 3, ∃ N(m) such that any set of n ≥ N(m) points in the plane, no three on a line, contains m points that are the vertices of a convex m-gon. ∀ m ≥ 3, ∃ N(m) such that any set of n ≥ N(m) points in the plane, no three on a line, contains m points that are the vertices of a convex m-gon. Theorem (Erdős-Szekeres 1935) N(m) = R3(2; m, m) |X| = R3(2; m, m) ￾S 3 ⇥ monochromatic ⇥f : ￾X 3 ⇥ ￾ {0, 1} X: set of points in the plane, no 3 on a line f({a, b, c}) = |￾abc| mod 2 ⇥a, b, c ￾ X, ￾abc: points in triangle abc a b c ￾S ￾ X, |S| = m

X:set of points in the plane,no 3 on a line Va,b,c∈X,△abc:points in triangle abc f({a,b,c})=△abe mod2 2 X=R(2;m,m)f:(3)→{0,1}3SCX,|S1=m S∈(X) monochromatic(③) S is a convex m-gon Otherwise,b disjoint union: Contradiction! △abe=△abdU△acdU△bcdU{d} f(abc)=f(abd)+f(acd)+f(bcd)+1 C

|X| = R3(2; m, m) ￾S 3 ⇥ monochromatic ⇥f : ￾X 3 ⇥ ￾ {0, 1} ⇥S ￾ ￾X m ⇥ X: set of points in the plane, no 3 on a line f({a, b, c}) = |￾abc| mod 2 ⇥a, b, c ￾ X, ￾abc: points in triangle abc a b c S is a convex m-gon Otherwise, a b c d ￾abc = ￾abd ⇥ ￾acd ⇥ ￾bcd disjoint union: f(abc) = f(abd) + f(acd) + f(bcd)+1 ￾{d} Contradiction! ￾S ￾ X, |S| = m