The ANZIAM Journal

Research Article

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

George Szekeresa1 and Lindsay Petersa2

a1 (deceased), School of Mathematics, University of NSW, Sydney NSW 2052, Australia.

a2 Pacific Knowledge Systems, Australian Technology Park, Eveleigh NSW 1430, Australia; e-mail: l.peters@pks.com.au.

Abstract

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.

(Received April 25 2006)

(Revised October 15 2006)

Keywords and phrases

  • Erdos-Szekeres problem;
  • Ramsey theory;
  • convex polygons and polyhedra;
  • generalized convexity