Equitable Rectangular Dissections of a Square

on YouTube ↗38m

" summary

Partitioning an n-by-n square into n lattice rectangles only makes sense when n is a power of two, and the edge-flip chain on those dissections is provably connected in that case. Restricting to dyadic tilings yields a counting recurrence a_k = 2 a_{k-1}^2 − a_{k-2}^4 (growth ≈ golden ratio^n) and a labeled VH tree bijection. With weight λ^{total edge length}, the dyadic chain mixes in O(n^2 log n) for λ<1 (path coupling with an exponential metric) and mixes exponentially slowly for λ>1; an alternative large-block rotation chain is rapidly mixing.

AI-written summary · about

" chapters (14)

1. 0:00Intro
2. 2:05Related Tiling Problems / Flip Chains
3. 4:01Background: Lattice Triangulations
4. 5:35Weighted Rectangular Dissections
5. 8:20Proof Sketch: Connectivity
6. 11:07Background: Dyadic Tilings
7. 14:09Stochastic Approaches: Dyadic Tilings
8. 15:11Results: Dyadic Tilings
9. 16:17Results: General Rectangular Dissections
10. 20:09Fast Mixing for Dyadic Tilings
11. 21:30Proof Sketches
12. 26:02The Bottleneck when i 1
13. 31:28With 180° Rotations
14. 34:34Summary and Open Problems