Existence thresholds and Ramsey properties of random posets

被引：7

作者：

Falgas-Ravry, Victor ^{[1
]}

Markstrom, Klas ^{[1
]}

Treglown, Andrew ^{[2
]}

Zhao, Yi ^{[3
]}

机构：

[1] Umea Univ, Dept Math & Math Stat, Umea, Sweden

[2] Univ Birmingham, Sch Math, Birmingham, W Midlands, England

[3] Georgia State Univ, Dept Math & Stat, Atlanta, GA 30303 USA

来源：

RANDOM STRUCTURES & ALGORITHMS | 2020年 / 57卷 / 04期

基金：

美国国家科学基金会; 英国工程与自然科学研究理事会; 瑞典研究理事会;

关键词：

boolean lattice; existence thresholds; Ramsey properties; random posets; RANDOM SUBSETS; FREE FAMILIES;

D O I：

10.1002/rsa.20952

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Let P (n) denote the power set of [n], ordered by inclusion, and let P(n, p) denote the random poset obtained from. (n) by retaining each element from P(n) independently at random with probability p and discarding it otherwise. Given any fixed poset F we determine the threshold for the property that P(n, p) contains F as an induced subposet. We also asymptotically determine the number of copies of a fixed poset F in. P(n). Finally, we obtain a number of results on the Ramsey properties of the random poset. P(n, p).

引用

页码：1097 / 1133

页数：37

共 33 条

[1]

[Anonymous], 1992, Ann. Appl. Probab.

[2] Boolean Lattices: Ramsey Properties and Embeddings [J].

Axenovich, Maria ;

Walzer, Stefan .

ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2017, 34 (02) :287-298

[3] Q2-free Families in the Boolean Lattice [J].

Axenovich, Maria ;

Manske, Jacob ;

Martin, Ryan .

ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2012, 29 (01) :177-191

[4] Applications of Graph Containers in the Boolean Lattice [J].

Balogh, Jozsef ;

Treglown, Andrew ;

Wagner, Adam Zsolt .

RANDOM STRUCTURES & ALGORITHMS, 2016, 49 (04) :845-872

[5] A random version of Spemer's theorem [J].

Balogh, Jozsef ;

Mycroft, Richard ;

Treglown, Andrew .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 2014, 128 :104-110

[6]

Bollobas B., 1981, Combinatorics (Swansea, 1981), P80

[7]

Bukh B, 2009, ELECTRON J COMB, V16

[8]

Chen H.B., ARXIV190911370

[9] Maximum-size antichains in random set-systems [J].

Collares, Mauricio ;

Morris, Robert .

RANDOM STRUCTURES & ALGORITHMS, 2016, 49 (02) :308-321

[10] Largest family without A ∨ B ⊆ C ∧ D [J].

De Bonis, A ;

Katona, GOH ;

Swanepoel, KJ .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 2005, 111 (02) :331-336

← 1 2 3 4 →