Abstract:
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.
Note: This talk begins with a pre-seminar (aimed at graduate students) at 3:30–4:00. The main talk starts at 4:10.
Join Zoom Meeting: https://washington.zoom.us/j/
Meeting ID: 915 4733 5974