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