# Happy endings for flip graphs

Someone asked me where I was going with flip graphs of grids, and I didn't know at the time. But I got a hint the other night, and now I think I can prove it: a point set has a partial cube flip graph if and only if it has no empty pentagon. I think I'll wait until writing it up more carefully to give details of the proof, but the significance of this (beyond being pretty) is that it means we can compute the flip distances for these point sets easily, compared to e.g. convex polygons where computation of flip distances is a famous open problem (see e.g. Sleator Thurston and Tarjan 1986). Also I think the proof is easier in this level of generality than it is for grids.

To keep this from being content-free, here's an example showing that point sets without empty pentagons can be complicated. One more level of inscribed pentagons and there would be an empty one... I also have several infinite families beyond the one we already knew, convex subsets of a projective transformation of a grid.