Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-22T08:01:24.344Z Has data issue: false hasContentIssue false
  • English
  • Français

Computer solution to the 17-point Erdős-Szekeres problem

Published online by Cambridge University Press:  17 February 2009

George Szekeres  and
Lindsay Peters
George Szekeres
Affiliation:
(deceased), School of Mathematics, University of NSW, Sydney NSW 2052, Australia.
Lindsay Peters
Affiliation:
Pacific Knowledge Systems, Australian Technology Park, Eveleigh NSW 1430, Australia; e-mail: [email protected].
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We describe a computer proof of the 17-point version of a conjecture originally made by Klein-Szekeres in 1932 (now commonly known as the “Happy End Problem”) that a planar configuration of 17 points, no 3 points collinear, always contains a convex 6-subset. The proof makes use of a combinatorial model of planar configurations, expressed in terms of signature functions satisfying certain simple necessary conditions. The proof is more general than the original conjecture as the signature functions examined represent a larger set of configurations than those which are realisable. Three independent implementations of the computer proof have been developed, establishing that the result is readily reproducible.

Keywords

Erdos-Szekeres problemRamsey theoryconvex polygons and polyhedrageneralized convexity
Type
Research Article
Information
The ANZIAM Journal , Volume 48 , Issue 2 , October 2006 , pp. 151 - 164
Copyright
Copyright © Australian Mathematical Society 2006

References

[1]Bonnice, W. E., “On convex polygons determined by a finite planar set”, Amer. Math. Monthly 81 (1974) 749–752.CrossRefGoogle Scholar
[2]Chung, F. R. K. and Graham, R. L., “Forced convex n-gons in the plane”, Discrete Comput. Geom. 19 (1998) 367–371, Special Issue.CrossRefGoogle Scholar
[3]Erdős, P. and Szekeres, G., “A combinatorial problem in geometry”, Compositio Math. 2 (1935) 463–470.Google Scholar
[4]Erdős, P. and Szekeres, G., “On some extremum problems in elementary geometry”, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 3–4 (1961) 53–63.Google Scholar
[5]Kalbfleisch, J. D., Kalbfleisch, J. G. and Stanton, R. G., “A combinatorial problem on convex regions”, in 1970 Proc. Louisiana Conf. on Combinatorics, Graph Theory and Computing, (Louisiana State Univ., Baton Rouge, 1970) 180–188.Google Scholar
[6]Knuth, D. E., Axioms and Hulls (Springer, Heidelberg, 1992).CrossRefGoogle Scholar
[7]Morris, W. and Soltan, V., “The Erdős-Szekeres problem on points in convex position. A survey”, Bull. Amer. Math. Soc. (N.S.) 37 (2000) 437–458.CrossRefGoogle Scholar
[8]Toth, G. and Valtr, P., “The Erdős-Szekeres theorem: upper bounds and related results”, in Combinatorial and computational geometry, Math. Sci. Res. Inst. Publ. 52, (Cambridge Univ. Press, Cambridge, 2005) 557–568.Google Scholar
[9]Wilson, R. M. and van Lint, J. H., A Course in Combinatorics (Cambridge Univ. Press, New York, 1992).Google Scholar