THE PHASE TRANSITION FOR DYADIC TILINGS

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 -> infinity, 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.

Holroyd, A. E. (author)
Kozma, G. (author)
Wästlund, Johan,1971Gothenburg University,Göteborgs universitet,Institutionen för matematiska vetenskaper, matematik,Department of Mathematical Sciences, Mathematics,Chalmers tekniska högskola,Chalmers University of Technology,University of Gothenburg(Swepub:cth)wastlund (author)
Winkler, P. (author)
Göteborgs universitetInstitutionen för matematiska vetenskaper, matematik (creator_code:org_t)

In:Transactions of the American Mathematical Society366:2, s. 1029-10460002-99471088-6850

By the author/editor: Angel, O.; Holroyd, A. E.; Kozma, G.; Wästlund, Johan, ...; Winkler, P.

About the subject

By the university: University of Gothenburg; Chalmers University of Technology

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.