Maximum-size antichains in random set-systems

被引：10

作者：

Collares, Mauricio ^{[1
]}

Morris, Robert ^{[1
]}

机构：

[1] IMPA, Estr Dona Castorina 110, Rio De Janeiro, RJ, Brazil

来源：

RANDOM STRUCTURES & ALGORITHMS | 2016年 / 49卷 / 02期

关键词：

Hypergraph containers; antichains; random set-systems; RANDOM SUBSETS;

D O I：

10.1002/rsa.20647

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We show that, for pn, the largest set in a p-random sub-family of the power set of {1,...,n} containing no k-chain has size (k-1+o(1))p() with high probability. This confirms a conjecture of Osthus. (c) 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 308-321, 2016

引用

页码：308 / 321

页数：14

共 21 条

[1]

[Anonymous], 1963, Teor. Verojatnost. i Primenen

[2]

Balogh J, 2015, J AM MATH SOC, V28, P669

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

Balogh, Jozsef ;

Mycroft, Richard ;

Treglown, Andrew .

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

[4] ON GENERALIZED GRAPHS [J].

BOLLOBAS, B .

ACTA MATHEMATICA ACADEMIAE SCIENTIARUM HUNGARICAE, 1965, 16 (3-4) :447-&

[5]

Conlon andW D., ANN MATH IN PRESS

[6] Sperner's Theorem and a Problem of Erdos, Katona and Kleitman [J].

Das, Shagnik ;

Gan, Wenying ;

Sudakov, Benny .

COMBINATORICS PROBABILITY & COMPUTING, 2015, 24 (04) :585-608

[7] ON A LEMMA OF LITTLEWOOD AND OFFORD [J].

ERDOS, P .

BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1945, 51 (12) :898-902

[8]

Kleitman D., 1968, P C, P215

[9] The width of random subsets of boolean lattices [J].

Kohayakawa, Y ;

Kreuter, B .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 2002, 100 (02) :376-386

[10]

Kohayakawa Y, 2000, RANDOM STRUCT ALGOR, V16, P177, DOI 10.1002/(SICI)1098-2418(200003)16:2<177::AID-RSA4>3.0.CO

← 1 2 3 →