Hypercube percolation

Onderzoeksoutput: Boek/rapportRapportAcademic

28 Downloads (Pure)

Uittreksel

We study bond percolation on the Hamming hypercube {0,1}^m around the critical probability p_c. It is known that if p=p_c(1+O(2^{-m/3})), then with high probability the largest connected component C_1 is of size Theta(2^{2m/3}) and that this quantity is non-concentrated. Here we show that for any sequence eps_m such that eps_m=o(1) but eps_m >> 2^{-m/3} percolation on the hypercube at p_c(1+eps_m) has |C_1| = (2+o(1)) eps_m 2^m and |C_2| = o(eps_m 2^m) with high probability, where C_2 is the second largest component. This resolves a conjecture of Borgs, Chayes, the first author, Slade and Spencer [17].
Originele taal-2Engels
Plaats van productieEindhoven
UitgeverijEurandom
Aantal pagina's71
StatusGepubliceerd - 2013

Publicatie series

NaamReport Eurandom
Volume2013027
ISSN van geprinte versie1389-2355

Vingerafdruk

Hypercube
Critical Probability
M-sequence
Connected Components
Resolve

Citeer dit

Hofstad, van der, R. W., & Nachmias, A. (2013). Hypercube percolation. (Report Eurandom; Vol. 2013027). Eindhoven: Eurandom.
Hofstad, van der, R.W. ; Nachmias, A. / Hypercube percolation. Eindhoven : Eurandom, 2013. 71 blz. (Report Eurandom).
@book{c91157eb28e8451191f20859f01ade11,
title = "Hypercube percolation",
abstract = "We study bond percolation on the Hamming hypercube {0,1}^m around the critical probability p_c. It is known that if p=p_c(1+O(2^{-m/3})), then with high probability the largest connected component C_1 is of size Theta(2^{2m/3}) and that this quantity is non-concentrated. Here we show that for any sequence eps_m such that eps_m=o(1) but eps_m >> 2^{-m/3} percolation on the hypercube at p_c(1+eps_m) has |C_1| = (2+o(1)) eps_m 2^m and |C_2| = o(eps_m 2^m) with high probability, where C_2 is the second largest component. This resolves a conjecture of Borgs, Chayes, the first author, Slade and Spencer [17].",
author = "{Hofstad, van der}, R.W. and A. Nachmias",
year = "2013",
language = "English",
series = "Report Eurandom",
publisher = "Eurandom",

}

Hofstad, van der, RW & Nachmias, A 2013, Hypercube percolation. Report Eurandom, vol. 2013027, Eurandom, Eindhoven.

Hypercube percolation. / Hofstad, van der, R.W.; Nachmias, A.

Eindhoven : Eurandom, 2013. 71 blz. (Report Eurandom; Vol. 2013027).

Onderzoeksoutput: Boek/rapportRapportAcademic

TY - BOOK

T1 - Hypercube percolation

AU - Hofstad, van der, R.W.

AU - Nachmias, A.

PY - 2013

Y1 - 2013

N2 - We study bond percolation on the Hamming hypercube {0,1}^m around the critical probability p_c. It is known that if p=p_c(1+O(2^{-m/3})), then with high probability the largest connected component C_1 is of size Theta(2^{2m/3}) and that this quantity is non-concentrated. Here we show that for any sequence eps_m such that eps_m=o(1) but eps_m >> 2^{-m/3} percolation on the hypercube at p_c(1+eps_m) has |C_1| = (2+o(1)) eps_m 2^m and |C_2| = o(eps_m 2^m) with high probability, where C_2 is the second largest component. This resolves a conjecture of Borgs, Chayes, the first author, Slade and Spencer [17].

AB - We study bond percolation on the Hamming hypercube {0,1}^m around the critical probability p_c. It is known that if p=p_c(1+O(2^{-m/3})), then with high probability the largest connected component C_1 is of size Theta(2^{2m/3}) and that this quantity is non-concentrated. Here we show that for any sequence eps_m such that eps_m=o(1) but eps_m >> 2^{-m/3} percolation on the hypercube at p_c(1+eps_m) has |C_1| = (2+o(1)) eps_m 2^m and |C_2| = o(eps_m 2^m) with high probability, where C_2 is the second largest component. This resolves a conjecture of Borgs, Chayes, the first author, Slade and Spencer [17].

M3 - Report

T3 - Report Eurandom

BT - Hypercube percolation

PB - Eurandom

CY - Eindhoven

ER -

Hofstad, van der RW, Nachmias A. Hypercube percolation. Eindhoven: Eurandom, 2013. 71 blz. (Report Eurandom).