This research explores the discovery of symmetrical realizations of convex-hexagon-free point placements on 16 points using satisfiability solving techniques. The central focus is on identifying point configurations that exhibit 3-, 4-, and 5-fold rotational symmetry. These 16 point configurations correspond to the maximal number of points that can be placed in the Euclidean plane in general position without forming any convex hexagons, a central case in the study of the Erdös–Szekeres conjecture , a foundational problem in combinatorial geometry.

Building on previous work in combinatorial geometry and SAT-based combinatorial methods, this research extends existing Boolean satisfiability encodings by incorporating symmetry constraints and structural conditions specific to the hexagon-free problem. Using these ideas, new conjunctive normal form formulas are developed to represent the search space of symmetric hexagon-free point placements.

To interpret and visualize solutions, satisfying assignments to these CNFs are passed through a point realization tool that reconstructs geometric configurations from orientation triple data. This enables the conversion of logical encodings into concrete point placements that can be analyzed and compared. Structural analysis of these placements includes examining the frequency and distribution of smaller convex polygons, such as 4-gons and 5-gons, to better understand the local geometric implications of hexagon avoidance.

The resulting symmetric configurations, especially those with four-fold and five-fold symmetry, represent some of the first structured, realizable examples of 16-point hexagon-free sets. These findings contribute new insight into the Erdös–Szekeres conjecture and offer a stepping stone toward understanding larger generalizations, such as the existence of 32-point configurations that avoid convex 7-gons.

65 pages

Thesis Committee:
Marijn Heule (Chair)
Ruben Martins

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu