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".

  • $\begingroup$ What if all these points are arranged on the same line? Does that count as convex pentagon? $\endgroup$ – Evgeny Mar 17 '17 at 8:08
  • $\begingroup$ Yes, forgot to add that there are no 3 points on the same line. $\endgroup$ – sooobus Mar 17 '17 at 8:13
  • $\begingroup$ Can you prove the milder claim that at a convex quadrilateral exists? $\endgroup$ – Chris Culter Mar 17 '17 at 8:17
  • $\begingroup$ Yes, I can prove that in the set of 5 points a convex quadrilateral exists. $\endgroup$ – sooobus Mar 17 '17 at 8:19
  • $\begingroup$ 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. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ I didn't understand: which objects form a sequence? $\endgroup$ – sooobus Mar 17 '17 at 8:45
  • $\begingroup$ 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. $\endgroup$ – Mees de Vries Mar 17 '17 at 8:49
  • $\begingroup$ @MeesdeVries: that is true, I should have said "Erdos&co. opened the main road to the solution through the following technique". $\endgroup$ – Jack D'Aurizio Mar 17 '17 at 8:50
  • $\begingroup$ Okay, I know about this problem, but I think that my case should be proven in the easier way. $\endgroup$ – sooobus Mar 17 '17 at 8:54
  • $\begingroup$ @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. $\endgroup$ – Jack D'Aurizio Mar 17 '17 at 8:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.