THE PHASE TRANSITION FOR DYADIC TILINGS

被引：0

作者：

Angel, Omer ^{[1
]}

Holroyd, Alexander E. ^{[2
]}

Kozma, Gady ^{[3
]}

Wastlund, Johan ^{[4
]}

Winkler, Peter ^{[5
]}

机构：

[1] Univ British Columbia, Dept Math, Vancouver, BC V6T 1Z2, Canada

[2] Microsoft Res, Redmond, WA 98052 USA

[3] Weizmann Inst Sci, IL-76100 Rehovot, Israel

[4] Chalmers, Dept Math Sci, S-41296 Gothenburg, Sweden

[5] Dartmouth Coll, Dept Math, Hanover, NH 03755 USA

来源：

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY | 2014年 / 366卷 / 02期

基金：

美国国家科学基金会; 以色列科学基金会; 加拿大自然科学与工程研究理事会;

关键词：

Dyadic rectangle; tiling; phase transition; percolation; generating function; ZERO-ONE LAW; UNIT SQUARE;

D O I：

暂无

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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.

引用

页码：1029 / 1046

页数：18

共 9 条

[1]

[Anonymous], 1960, Mathematical Proceedings of the Cambridge Philosophical Society, DOI DOI 10.1017/S0305004100034241

[2]

Coffman EG, 2001, PROBAB THEORY REL, V120, P585

[3] Every monotone graph property has a sharp threshold [J].

Friedgut, E ;

Kalai, G .

PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 1996, 124 (10) :2993-3002

[4] Random dyadic tilings of the unit square [J].

Janson, S ;

Randall, D ;

Spencer, J .

RANDOM STRUCTURES & ALGORITHMS, 2002, 21 (3-4) :225-251

[5]

Janson S., 2001, REMARKS RANDOM DYADI

[6] Counting dyadic equipartitions of the unit square [J].

Lagarias, JC ;

Spencer, JH ;

Vinson, JP .

DISCRETE MATHEMATICS, 2002, 257 (2-3) :481-499

[7] AN APPROXIMATE ZERO-ONE LAW [J].

RUSSO, L .

ZEITSCHRIFT FUR WAHRSCHEINLICHKEITSTHEORIE UND VERWANDTE GEBIETE, 1982, 61 (01) :129-139

[8] ON RUSSOS APPROXIMATE ZERO-ONE LAW [J].

TALAGRAND, M .

ANNALS OF PROBABILITY, 1994, 22 (03) :1576-1587

[9] A note on the norms of transition operators on lamplighter graphs and groups [J].

Woess, W .

INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 2005, 15 (5-6) :1261-1272

← 1 →