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?)

  • 1. E. G. Coffman, Jr., G. S. Lueker, J. Spencer, and P. M. Winkler.
    Packing random rectangles.
    Probab. Theory Related Fields, 120(4):585-599, 2001.,$ ^{\sim }$egc. MR 1853484 (2003c:90045)
  • 2. E. Friedgut and G. Kalai.
    Every monotone graph property has a sharp threshold.
    Proc. Amer. Math. Soc., 124(10):2993-3002, 1996. MR 1371123 (97e:05172)
  • 3. T. E. Harris.
    A lower bound for the critical probability in a certain percolation process.
    Proc. Cambridge Philos. Soc., 56:13-20, 1960. MR 0115221 (22:6023)
  • 4. S. Janson.
    Remarks to random dyadic tilings of the unit square, 2001.
    Preprint,$ ^{\sim }$svante.
  • 5. S. Janson, D. Randall, and J. Spencer.
    Random dyadic tilings of the unit square.
    Random Structures Algorithms, 21(3-4):225-251, 2002.
    Random structures and algorithms (Poznan, 2001).,$ ^{\sim }$svante. MR 1945369 (2003k:60018)
  • 6. J. C. Lagarias, J. H. Spencer, and J. P. Vinson.
    Counting dyadic equipartitions of the unit square.
    Discrete Math., 257(2-3):481-499, 2002. MR 1935743 (2003h:05018)
  • 7. L. Russo.
    An approximate zero-one law.
    Z. Wahrsch. Verw. Gebiete, 61(1):129-139, 1982. MR 671248 (84e:60153)
  • 8. M. Talagrand.
    On Russo's approximate zero-one law.
    Ann. Probab., 22(3):1576-1587, 1994. MR 1303654 (96g:28009)
  • 9. W. Woess.
    A note on the norms of transition operators on lamplighter graphs and groups.
    Internat. J. Algebra Comput., 15(5-6):1261-1272, 2005. MR 2197832 (2007b:05101)

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