Prove that enough points in the plane guarantee there is a convex hexagon

75 Views Asked by At

Prove that if we draw enough points in the plane (no collinear triplets), then there will be six such points that form a convex hexagon.

I tried to draw points in a plane sheet, trying to avoid the formation of the convex hexagon, but I can't do that, I just don't understand why. I think that with 8 points there is already necessarily a convex hexagon. There is no way to avoid, I guess (but I may be wrong!).

1

There are 1 best solutions below

0
On BEST ANSWER

This is a special case of a result due to Erdos-Szekeres. They have proven the following theorem: For any integer, $n\geq 3$ there exists a positive integer $r(n)$ such that any set of at least $r(n)$ points in general position in the plane, i.e. no three of them are on a line, contains $n$ points that are the vertices of a convex $n$-gon.

The proof of Erdos and Szekeres is based on the Ramsey Theory and you can bound from above the number $r(n)$ by some Ramsey number. If you want a references here

https://www.ams.org/journals/bull/2000-37-04/S0273-0979-00-00877-6/S0273-0979-00-00877-6.pdf