Introduction

Frank Ramsey (born in 1903) remains one of the iconic figures in mathematics whose ideas would spark the creation of a field known today as Ramsey Theory. Paul Erdos (born in 1913) however is given credit as being the father of modern day Ramsey Theory. Erdos would make significant and numerous contributions to Ramsey theory and other fields such as number theory, combinatorics, set theory, and mathematical analysis, where in his lifetime he would write and/or co-author over 1500 mathematical articles (A. Soifer 2009). Ramsey theory remains an active field of research today, attracting mathematicians in part through the relative ease in interpreting the problem, and perhaps making the first few steps towards a proof with only a basic level of mathematical background often required, while simultaneously exhibiting extreme complexity in formulating generalized and closed proofs.

In 1935 Erdos and Szekers proved the following theorem:

For any positive integer N>3, any sufficiently large finite set of M points S={(x₁, y₁ ),… ,( x_M, y_M )} in the 2D plane in general position has a subset of N points that form vertices of a convex polygon (N-gon).

Question?

This theorem proposes that there exists a minimum number of M₀ points in general position, no three of whom can be connected by a line, which are needed to guarantee all possible N-gon’s are convex. We know that a minimum of M_o=9 points in general position is required to guarantee the existence of a convex pentagon, denoted by f(5)=9. By the above theorem there should exist configurations of fewer than 9 points in which no convex pentagon can be drawn. Particularly, it can be shown that there exist configurations of n=8 points in which NO convex pentagons can be formed. Similarly, it can be shown that f(4)=5 and f(6)=17. In the latter case, 16 points in general position can be chosen in such a way that NO convex hexagons can be drawn … but not 17 points through!

Our goal!

The goal of this webpage is to allow the user to attempt to input n points N < n < M₀ (n=4,8,or 16 particularly) in general position so that no convex N-gons with N=4,5,or 6 vertices can be found, respectively. This is a non-trivial problem computationally because there are n-choose-N combinations of vertices forming N-gons, which amounts to checking all 1, 56, or 9152 respective N-gons to ensure no convex N-gons can be found. The program has been generalized to detect the existence/nonexistence of convex polygons with up to 6 vertices.

Instruction

Select the order of the N-gon in the App tab. Try to enter a configuration of n points in general position either by clicking on the window, or by manually entering them in the interface (integers on [0,600]x[0,400]), so that all possible N-gon configurations are NOT convex.

More

Click here to learn more about the Happy Ending Problem!

The figure above is a configuration of 16 points in general position without a convex 6-gon.

References

[1] Alexander Soifer, “The Mathematical Colouring Book,” College of Letters, Arts and Sciences, University of Colorado, CO 80918, USA (2009)

[2] Configuration of 16 points is from Michael Mossinghoff