Introduction to Ramsey Theory: Students' Projects

Chapter 26 Happy Ending Problem Applet

\(\textbf{Summary:}\) In 1935 Erdős and Szekeres proved the following theorem:

For any positive integer \(N\text{,}\) any sufficiently large finite set of \(M\) points \(S = \{(x_1,y_1),\ldots,(x_m,y_m)\}\) in the plane in general position has a subset of \(N\) points that form vertices of a convex \(N\)–gon.

Particularly, we know that a minimum of \(9\) points in general position is required to guarantee the existence of a convex pentagon, \(f(5)=9\text{.}\) By Erdős–Szekeres theorem, there exists configurations of fewer than 9 points in which no convex pentagon can be drawn. It can be shown that there exist configurations of 8 points in which NO convex pentagons can be formed.

The goal of this project was to design an interactive web–app where the user attempts to input \(N\) points (\(N=8\) particularly) in general position in which no convex pentagons can be found. This is a nontrivial problem computationally because there are 8–choose–5 combinations, or 56 possible pentagons one needs to check to ensure no convex pentagons can be formed from a set of 8 properly arranged points in general position. The code was also generalized to detect the existence of a convex quadrilateral (\(N=4\)) and a convex hexagon (\(N=6\)).

Below we outline the general ideas behind our code and detection protocols in the case of \(N=5\text{.}\)

• User inputs \(M\) points \(S = \{(x_1,y_1),\ldots,(x_m,y_m)\}\) in general position in an interactive display.

• User has an opportunity to try to avoid forming a convex pentagon.

• The built in pentagon detection algorithm alerts the user once when a convex pentagon is found.

The basic structure of the algorithm involves selecting a \(5\)–element subset of \(S\text{,}\) ordering the subset in a counter clockwise arrangement, detection of the convexity or concavity. If the former, done, if the latter then a new unique 5 element set is generated and the algorithm repeats till a convex set is found. If no convex set is found then the program returns a congratulatory message.

Basic structure details:

1. From the indices \(I=\{1,2,\ldots,M\}\) the set of all \(5\)–term combinations are generated \(I_i=\{a,b,c,d,e\}\text{,}\) where \(a,b,c,d,e\) are unique indices in \(I\) and \(i=1,2,\ldots, \binom{M}{5}\text{,}\) giving us a set of five elements \(S(I_i)=\{(x_a,y_a),(x_b,y_b),\ldots,(x_e,y_e)\}=\{\vec{r}_a, \vec{r}_b,\ldots, \vec{r}_e\}\text{,}\) for a chosen \(I_i\text{.}\)

2. There are \(\binom{5}{2}=10\) different ways of connecting all points in the set \(S(I_i)\text{,}\) only one of which forming a pentagon. As will be outlined below, the ordering of these points must be established to “draw” the edges defining the encircling pentagon: a counter clock wise arrangement is chosen.

3. Ordering: Define the mean of the set \(S(I_i)\) as \(\overline{\vec{r}}_i=\text{average}(S(I_i))=(\overline{x},\overline{y})\) and define the vector \(\vec{d}_j=\vec{r}_j - \overline{\vec{r}}_i=(x_j-\overline{x},y_j-\overline{y})\) for all \(\vec{r}_j\in S(I_i)\text{,}\) as illustrated in Figure 26.0.1 (left).

   The angle made between the positive \(x\)–direction and \(\vec{d}_j\) is \(\theta_j\text{.}\) If \(y-\overline{y}\gt 0\) then \(\theta_j=\arccos((x_j-\overline{x})/h_j)\) where \(h_j=|\vec{d}_j|\text{.}\) If \(y-\overline{y}\lt 0\) then \(\theta_j=2\pi - \arccos((x_j-\overline{x})/h_j)\text{.}\)

   The set \(S(I_i)\) is then oriented in a counter clockwise (CC) fashion into a set of 2D vectors \(S(I_i^\prime)\) where \(I_i^\prime=CC(I_i)\) and \(CC:I_i\to I_i\) is our ordering function so as to yield a monotonic increase in \(\theta _j\) on \([0,2\pi)\text{.}\)

   An example of a CC ordered set of 5 points in the plane is illustrated in Figure 26.0.1 (right) where

   \begin{equation*} I_i^\prime=\{(x_{a_1},y_{a_1}), (x_{d_2},y_{d_2}),(x_{e_3},y_{e_3}),(x_{b_4},y_{b_4}),(x_{c_5},y_{c_5}). \end{equation*}

4. Now we define the set of CC oriented edges as vectors \(\vec{r}_m=(x_{k_{m+1}}-x_{j_m},y_{k_{m+1}}-y_{j_m})\text{,}\) where \(j,k\in I_i\text{.}\) We wish to define a new set of characteristic angles \(\phi_m\) of \(\vec{r}_m\text{.}\) If \(y_{k_{m+1}}-y_{j_m}\gt 0\) then \(\phi_m=\arccos((x_{k_{m+1}}-x_{j_m})/H_m)\) where \(H_m=|\vec{r}_m|\text{.}\) If \(y_{k_{m+1}}-y_{j_m}\lt 0\) then \(\theta_j=2\pi - \arccos((x_{k_{m+1}}-x_{j_m})/H_m)\text{.}\)

   A convex pentagon is detected if \(\phi_1\lt \phi_2\lt \phi_3\lt \phi_4\lt \phi_5\text{.}\) If there exist \(\phi_{m+1}\leq \phi_m\) the the pentagon is NOT convex and breaks this loop by selecting an new \(S(I_t)\) for \(t\not= i\text{.}\) In the case \(\phi_{m+1}=\phi_m\text{,}\) the given points are not in general position as 3–points can be connected with a straight line. An example of this is illustrated in Figure 26.0.1 (right) in which \(\phi_d\lt \phi_e\lt \phi_b\not\lt \phi_c\text{.}\)

5. The program continues selecting a new set \(S(I_t)\subset S\) for \(s\not= i\) until a convex pentagon is found or not found. If you are lucky enough to have chosen a set of 8 points so that no convex pentagon is found for all 56 combinations, the program responds saying “CONGRATULATIONS!”