Section 6.1 Erdős-Szekeres Problem of Convex Polygons
Where there is love there is life. — Mahatma Gandhi, Indian leader, 1869 — 1948
Warm Up. Consider a finite set of points \(S\) in the plane, and ask, for example, this question: Is it true that there will always be a set of three points in \(S\) that are the vertices of a triangle?
Points in General Position in Plane. We say that the set of points \(A\) in the plane is in general position if there is no line that contains three points from \(A\text{.}\) See Figure 6.1.1.
Problem. For any integer \(n\geq 3\text{,}\) determine the smallest positive integer \(N(n)\) such that any set of at least \(N(n)\) points in general position in the plane (i.e., no three of the points are on a line) contains \(n\) points that are the vertices of a convex \(n\)-gon.
Convex \(n\)-gon. A convex \(n\)-gon is an \(n\)-gon with the property that if two points \(A\) and \(B\) are inside of the \(n\)-gon then the whole segment \(\overline{AB}\) is inside of the \(n\)-gon. See Figure 6.1.2.
Example 6.1.3.
\(N(3)=3\text{.}\)
Example 6.1.4.
\(n=4\text{.}\) In 1932 Esther Klein made the following observation: Among any five points in general position in the Euclidean plane, it is always possible to select four points that form the vertices of a convex quadrilateral.
Proof: The convex hull of a set of points \(S\) in the Euclidean plane is the smallest convex polygon that encloses all points from \(S\text{.}\)
Question 6.1.6.
Is it possible to find four points in the plane that do not form a convex quadrilateral?
Therefore… \(N(4)=\)
\(n=5\text{.}\) See Figures 6.1.7 an d 6.1.8.
Therefore … \(N(5)\geq 9\text{.}\)
\(n=5\) … Part II Let \(S\) be a set of nine points in the plane in general position. Let \(\overline{S}\) be the convex hull of \(S\text{.}\)
-
If \(\overline{S}\) has five or more vertices, we are done. See Figure 6.1.9.
Figure 6.1.9. The convex hull of \(S\) has six points. Let the convex hull \(\overline{S}\text{,}\) the convex hull of \(S\text{,}\) has three or four vertices. Then the set \(T=S\backslash \overline{S}\) contains six or five (remaining) points of \(S\) and they are all inside of \(\overline{S}\text{.}\) Let \(\overline{T}\) be the convex hull of \(T\text{.}\)
-
If \(|\overline{T}|=5\) or \(|\overline{T}|=6\)… Done! See Figure 6.1.10.
Figure 6.1.10. Example: \(|S|=|\{A,B,\ldots,I\}|=9\text{,}\) \(|\overline{S}|=|\{A,B,C\}|=3\text{,}\) \(|T|=|\{D,E,\ldots,I\}|=6\text{,}\) and \(|\overline{T}|=|\{D,E,F,G,H\}|=5\text{.}\) -
For the remaining cases see Figure 6.1.11.
Figure 6.1.11. Four remaining cases.
Configuration of the type \((3, 3, 2)\text{.}\)
-
Consider the inside triangle and the line segment.
The line that contains the line segment intersects two sides of the triangle.
Notice the vertex where those two sides of the triangle intersect.
Draw rays starting at the end points of the line segment as on Figure 6.1.12
Figure 6.1.12. A triangle, a line segment, and four rays.
Three regions. Notice the three open regions in the plane on the Figure 6.1.13:
None of the three regions intersects the interior of the triangle
Region 1 and Region 2 intersect (part of the plane ‘above’ the top vertex.)
Region 3 does not intersect either Region 1 or Region 2.
Three points outside of the triangle. Note that the remaining three points in the configuration \(3-3-2\) cannot be on the boundary of any of Regions 1-3. (Why?) See Figure 6.1.14.
Configuration of the type \((3, 3, 3)\text{.}\) Note that the configuration the \(8\)-point configuration \((3,3,2)\) is contained in the configuration \((3,3,3)\text{.}\) See Figure 6.1.15.
Therefore the configuration of the type \((3, 3, 3)\) contains a convex pentagon.
Configuration of the type \((4, 3, 1)\text{.}\)
-
Consider a triangle and a single point inside of it, and note three regions, Figure 6.1.16.
Figure 6.1.16. Type \((\ast,3,1)\text{.}\) -
By the Pigeonhole Principle, at least two of the remaining four points must belong to the same region, say Region 2. See Figure 6.1.17.
Figure 6.1.17. There is a convex pentagon!
Configuration of the type \((4, 4, 1)\text{.}\) Note that the configuration \((4,4,1)\) contains the configuration \((4,3,1)\text{.}\) See Figure 6.1.18.
Configuration of the type \((4, 3, 2)\text{.}\) Note that the configuration \((4,3,2)\) contains the configuration \((4,3,1)\text{.}\) See Figure 6.1.19.
Configuration of the type \((3, 4, 2)\text{.}\) Consider the inside quadrilateral and the line segment. See Figures 6.1.20 — Figure 6.1.22.
Therefore