# In any set of 9 points in $\mathbb{R}^2$ a convex pentagon exists

In any set of 9 points in $\mathbb{R}^2$ with no triple of points on the same line a convex pentagon exists.

My attempt: I suppose I need to consider some convex hulls. If the convex hull has $\geq 5$ points, just take it. Else consider convex hull of the points inside. Here I don't understand how to finish the "bruteforce".

• What if all these points are arranged on the same line? Does that count as convex pentagon? – Evgeny Mar 17 '17 at 8:08
• Yes, forgot to add that there are no 3 points on the same line. – sooobus Mar 17 '17 at 8:13
• Can you prove the milder claim that at a convex quadrilateral exists? – Chris Culter Mar 17 '17 at 8:17
• Yes, I can prove that in the set of 5 points a convex quadrilateral exists. – sooobus Mar 17 '17 at 8:19
• Okay, you can do sort-of the same thing, but broken into a few different cases depending on ($x$) the number of vertices of the convex hull, ($y$) the number of vertices of the convex hull of the points inside, and ($z$) the number of vertices inside the latter. – Chris Culter Mar 17 '17 at 8:45

Erdos&co solved the happy ending problem by considering the slopes of the sides of the convex envelope and applying the Erdos-Szekeres/Dilworth's theorem: every sequence with $n^2+1$ elements has a monotonic subsequence with $n+1$ elements.
• According to the Wikipedia article, they only showed that for each $n$-gon there must be a least $m$ such that $m$ points in general position always have an $n$-gon among them. Finding specific least values of $m$ is harder; in particular, the case $n = 5$ was apparently first published in 1970, 35 years later. – Mees de Vries Mar 17 '17 at 8:49
• @sooobus: I don't think so, but with nowadays computer super-powers the case $m=5$ is easy to crack by brute force, since the space of configurations is not that large. – Jack D'Aurizio Mar 17 '17 at 8:56