Connectivity threshold for random subgraphs of the Hamming graph

Onderzoeksoutput: Boek/rapportRapportAcademic

71 Downloads (Pure)

Uittreksel

We study the connectivity of random subgraphs of the $d$-dimensional Hamming graph $H(d, n)$, which is the Cartesian product of $d$ complete graphs on $n$ vertices. We sample the random subgraph with an i.i.d.\ Bernoulli bond percolation on $H(d,n)$ with parameter $p$. We identify the window of the transition: when $ np- \log n \to - \infty$ the probability that the graph is connected goes to $0$, while when $ np- \log n \to + \infty$ it converges to $1$. We also investigate the connectivity probability inside the critical window, namely when $ np- \log n \to t \in \mathbb{R}$. We find that the threshold does not depend on $d$, unlike the phase transition of the giant connected component the Hamming graph (see [Bor et al, 2005]). Keywords: connectivity threshold, percolation, random graph, critical window
Originele taal-2Engels
Uitgeverijs.n.
Aantal pagina's9
StatusGepubliceerd - 2015

Publicatie series

NaamarXiv
Volume1504.05350 [math.PR]

Vingerafdruk

Hamming Graph
Subgraph
Connectivity
Giant Component
Percolation Threshold
Cartesian product
Random Graphs
Connected Components
Bernoulli
Complete Graph
Phase Transition
Converge
Graph in graph theory

Citeer dit

@book{3f1c99b73c2f4f62b5ef582ab5932892,
title = "Connectivity threshold for random subgraphs of the Hamming graph",
abstract = "We study the connectivity of random subgraphs of the $d$-dimensional Hamming graph $H(d, n)$, which is the Cartesian product of $d$ complete graphs on $n$ vertices. We sample the random subgraph with an i.i.d.\ Bernoulli bond percolation on $H(d,n)$ with parameter $p$. We identify the window of the transition: when $ np- \log n \to - \infty$ the probability that the graph is connected goes to $0$, while when $ np- \log n \to + \infty$ it converges to $1$. We also investigate the connectivity probability inside the critical window, namely when $ np- \log n \to t \in \mathbb{R}$. We find that the threshold does not depend on $d$, unlike the phase transition of the giant connected component the Hamming graph (see [Bor et al, 2005]). Keywords: connectivity threshold, percolation, random graph, critical window",
author = "L. Federico and {Hofstad, van der}, R.W. and T. Hulshof",
year = "2015",
language = "English",
series = "arXiv",
publisher = "s.n.",

}

Connectivity threshold for random subgraphs of the Hamming graph. / Federico, L.; Hofstad, van der, R.W.; Hulshof, T.

s.n., 2015. 9 blz. (arXiv; Vol. 1504.05350 [math.PR]).

Onderzoeksoutput: Boek/rapportRapportAcademic

TY - BOOK

T1 - Connectivity threshold for random subgraphs of the Hamming graph

AU - Federico, L.

AU - Hofstad, van der, R.W.

AU - Hulshof, T.

PY - 2015

Y1 - 2015

N2 - We study the connectivity of random subgraphs of the $d$-dimensional Hamming graph $H(d, n)$, which is the Cartesian product of $d$ complete graphs on $n$ vertices. We sample the random subgraph with an i.i.d.\ Bernoulli bond percolation on $H(d,n)$ with parameter $p$. We identify the window of the transition: when $ np- \log n \to - \infty$ the probability that the graph is connected goes to $0$, while when $ np- \log n \to + \infty$ it converges to $1$. We also investigate the connectivity probability inside the critical window, namely when $ np- \log n \to t \in \mathbb{R}$. We find that the threshold does not depend on $d$, unlike the phase transition of the giant connected component the Hamming graph (see [Bor et al, 2005]). Keywords: connectivity threshold, percolation, random graph, critical window

AB - We study the connectivity of random subgraphs of the $d$-dimensional Hamming graph $H(d, n)$, which is the Cartesian product of $d$ complete graphs on $n$ vertices. We sample the random subgraph with an i.i.d.\ Bernoulli bond percolation on $H(d,n)$ with parameter $p$. We identify the window of the transition: when $ np- \log n \to - \infty$ the probability that the graph is connected goes to $0$, while when $ np- \log n \to + \infty$ it converges to $1$. We also investigate the connectivity probability inside the critical window, namely when $ np- \log n \to t \in \mathbb{R}$. We find that the threshold does not depend on $d$, unlike the phase transition of the giant connected component the Hamming graph (see [Bor et al, 2005]). Keywords: connectivity threshold, percolation, random graph, critical window

M3 - Report

T3 - arXiv

BT - Connectivity threshold for random subgraphs of the Hamming graph

PB - s.n.

ER -