UW Combinatorics and Geometry Seminar: Corrine Yap

The mathematics of origami, or paper folding, raises rich questions in combinatorics and computational geometry, particularly related to flat-foldability: given a crease pattern, represented as a planar graph, and an assignment of mountains and valleys to the creases, can the configuration fold flat? Perhaps surprisingly, this decision problem for “global” flat-foldability is NP-hard in general. In contrast, “local" flat-foldability (folding flat in a small ball around each vertex) can be characterized by a few simple combinatorial conditions.

In this talk, we’ll present a new probabilistic perspective on flat-foldable origami. We consider the uniform distribution on locally flat-foldable crease patterns and a natural Markov chain called the face-flip chain which approximately samples from this distribution. We prove that this chain mixes rapidly for several natural families of origami tessellations—the square twist, the square grid, and the Miura-ori—as well as for the single-vertex crease pattern. We also show that on the square grid, a random locally flat-foldable configuration is exponentially unlikely to be globally flat-foldable. Joint work with Tom Hull and Marcus Michelen.

The pre-seminar will be a crash course on Markov chains and approximate sampling. No familiarity with origami will be assumed for either talk.