Proof involving Ramsey numbers

437 Views Asked by At

$S$ is a set of R(m,m;3) points in the plane in which no 3 points are collinear. I am trying to prove that $S$ contains $m$ points that form a convex $m$-gon.

I have tried using similar logic to the Happy Ending Problem but I can't come up with an argument to apply to this problem.

Edit: I have started trying to apply an argument by defining the coloring of monochromatic triangles of points being based on whether the amount of points inside the triangle is even or odd. For example if a triangle has 2 points in it color it red, and if it has 3 points in it color it blue. I am getting pretty close however I can't seem to connect the dots on why there must be a convex m-gon.

1

There are 1 best solutions below

5
On BEST ANSWER

It seems the following.

Enumerate points in an arbitrary order. Color a triangle of the points red, if starting from its vertex with the smallest number and going clockwise we visit its vertices in increasing order, and color it blue, otherwise. Ramsey Theorem implies that there exists a set $S’\subset S$ of $m$ points and a color $c$ such that all the triangles formed by vertices of the set $S’$ are colored by $c$. If $S’$ is not the set of vertices of a convex $m$-gon then, by Carathéodory theorem, :-) there exists a triangle formed by vertices of the set $S’$ containing another vertex of the set $S’$. A simple check shows that it is impossible.