The giant component after percolation of product graphs

被引：3

作者：

Lichev, Lyuben ^{[1
]}

机构：

[1] Ecole Normale Super Lyon, Lyon, France

来源：

JOURNAL OF GRAPH THEORY | 2022年 / 99卷 / 04期

关键词：

giant component; percolation; product graph; random graph; sharp threshold; RANDOM SUBGRAPHS; FINITE GRAPHS; ISOPERIMETRIC-INEQUALITIES; EVOLUTION;

D O I：

10.1002/jgt.22758

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In this paper we show the existence of a sharp threshold for the appearance of a giant component after percolation of Cartesian products of graphs under assumptions on their maximum degrees and their isoperimetric constants. In particular, this generalises a work of Ajtai, Komlos and Szemeredi from 1982 concerning percolation of the hypercube in high dimension.

引用

页码：651 / 670

页数：20

共 23 条

[1] LARGEST RANDOM COMPONENT OF A K-CUBE
AJTAI, M
KOMLOS, J
SZEMEREDI, E
[J]. COMBINATORICA, 1982, 2 (01) : 1 - 7
[2] Aldous D, 1997, ANN PROBAB, V25, P812
[3] Percolation on finite graphs and isoperimetric inequalities
Alon, N
Benjamini, I
Stacey, A
[J]. ANNALS OF PROBABILITY, 2004, 32 (3A) : 1727 - 1745
[4] [Anonymous], 2011, RANDOM GRAPHS
[5] Blaszczyszyn B., 2017, LECT NOTES RANDOM GE
[6] THE EVOLUTION OF RANDOM GRAPHS
BOLLOBAS, B
[J]. TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1984, 286 (01) : 257 - 274
[7] THE EVOLUTION OF RANDOM SUBGRAPHS OF THE CUBE
BOLLOBAS, B
KOHAYAKAWA, Y
LUCZAK, T
[J]. RANDOM STRUCTURES & ALGORITHMS, 1992, 3 (01) : 55 - 90
[8] Random subgraphs of finite graphs. II. The lace expansion and the triangle condition
Borgs, C
Chayes, JT
Van der Hofstad, R
Slade, G
Spencer, J
[J]. ANNALS OF PROBABILITY, 2005, 33 (05) : 1886 - 1944
[9] Random subgraphs of finite graphs: I. The scaling window under the triangle condition
Borgs, C
Chayes, JT
van der Hofstad, R
Slade, G
Spencer, J
[J]. RANDOM STRUCTURES & ALGORITHMS, 2005, 27 (02) : 137 - 184
[10] Random subgraphs of finite graphs:: III.: The phase transition for the n-cube
Borgs, Christian
Chayes, Jennifer T.
Van der Hofstad, Remco
Slade, Gordon
Spencer, Joel
[J]. COMBINATORICA, 2006, 26 (04) : 395 - 410

← 1 2 3 →