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