Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



The phase transition for dyadic tilings

Authors: Omer Angel, Alexander E. Holroyd, Gady Kozma, Johan Wästlund and Peter Winkler
Journal: Trans. Amer. Math. Soc. 366 (2014), 1029-1046
MSC (2010): Primary 05B45, 52C20, 60G18
Published electronically: September 10, 2013
MathSciNet review: 3130324
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A dyadic tile of order $ n$ is any rectangle obtained from the unit square by $ n$ successive bisections by horizontal or vertical cuts. Let each dyadic tile of order $ n$ be available with probability $ p$, independent of the others. We prove that for $ p$ sufficiently close to $ 1$, there exists a set of pairwise disjoint available tiles whose union is the unit square, with probability tending to $ 1$ as $ n\to \infty $, as conjectured by Joel Spencer in 1999. In particular, we prove that if $ p=7/8$, such a tiling exists with probability at least $ 1-(3/4)^n$. The proof involves a surprisingly delicate counting argument for sets of unavailable tiles that prevent tiling.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 05B45, 52C20, 60G18

Retrieve articles in all journals with MSC (2010): 05B45, 52C20, 60G18

Additional Information

Omer Angel
Affiliation: Department of Mathematics, University of British Columbia, Vancouver, British Columbia, Canada V6T 1Z2

Alexander E. Holroyd
Affiliation: Microsoft Research, 1 Microsoft Way, Redmond, Washington 98052

Gady Kozma
Affiliation: The Weizmann Institute of Science, Rehovot POB 76100, Israel

Johan Wästlund
Affiliation: Department of Mathematical Sciences, Chalmers University of Technology, S-412 96 Gothenburg, Sweden

Peter Winkler
Affiliation: Department of Mathematics, Dartmouth College, Hanover, New Hampshire 03755-3551

Keywords: Dyadic rectangle, tiling, phase transition, percolation, generating function
Received by editor(s): August 2, 2011
Received by editor(s) in revised form: July 20, 2012
Published electronically: September 10, 2013
Article copyright: © Copyright 2013 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society