5th Year Master's Thesis Presentation - Ethan Mackey

— 11:30am

Location:
In Person - Traffic21 Classroom, Gates Hillman 6501

Speaker:
ETHAN MACKEY , Master's Student, Computer Science Department, Carnegie Mellon University
https://www.linkedin.com/in/ethan-mackey-4391b6270

Pinwheels and Polygons: Symmetric Realizations of Polygon-Free Point Placements via SAT

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 Erdos–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 Erdos–Szekeres Conjecture and offer a stepping stone toward understanding larger generalizations, such as the existence of 32-point configurations that avoid convex 7-gons. 

Thesis Committee

Marijn Heule (Chair)
Ruben Martins

Additional Information

Add event to Google
Add event to iCal