Fetching the paper…

Reading the bibliography…

2014

The phase transition in site percolation on pseudo-random graphs

Krivelevich, Michael

Original
PDF
Post on X

Understand

We establish the existence of the phase transition in site percolation on pseudo-random $d$-regular graphs.

Let $G=(V,E)$ be an $(n,d,\lambda)$-graph, that is, a $d$-regular graph on $n$ vertices in which all eigenvalues of the adjacency matrix, but the first one, are at most $\lambda$ in their absolute values.
Form a random subset $R$ of $V$ by putting every vertex $v\in V$ into $R$ independently with probability $p$.
Then for any small enough constant $\epsilon>0$, if $p=\frac{1-\epsilon}{d}$, then with high probability all connected components of the subgraph of $G$ induced by $R$ are of size at most logarithmic in $n$, while for $p=\frac{1+\epsilon}{d}$, if the eigenvalue ratio $\lambda/d$ is small enough as a function of $\epsilon$, then typically $R$ spans a connected component of size at least $\frac{\epsilon n}{d}$ and a path of length proportional to $\frac{\epsilon^2n}{d}$.

The phase transition in site percolation on pseudo-random graphs · Around

Built on

P. Erdős and A. Rényi, On the evolution of random graphs
1960
Earlier work this paper cites.
M. Ajtai, J. Komlós and E. Szemerédi, The longest path in a random graph
1981
Earlier work this paper cites.
B. Bollobás, Y. Kohayakawa and T. Łuczak, On the evolution of random boolean functions, In: Extremal Problems for Finite Sets
1991
Earlier work this paper cites.
A. Frieze, M. Krivelevich and R. Martin, The emergence of a giant component in random subgraphs of pseudo-random graphs
2004
Earlier work this paper cites.

Similar

N. Alon and V. Rödl, Sharp bounds for some multicolor Ramsey numbers
2005
Cited alongside, same era.
M. Krivelevich and B. Sudakov, Pseudo-random graphs. In: More sets, graphs and numbers
2006
Cited alongside, same era.
N. Alon and J. H. Spencer, The probabilistic method
2008
Cited alongside, same era.

Then

C. M. Reidys, Large components in random induced subgraphs on n n -cubes
2009
Later among the works it cites.
M. Krivelevich and B. Sudakov, The phase transition in random graphs — a simple proof
2013
Later among the works it cites.
D. Sivakoff, Site percolation on the d d -dimensional Hamming torus
Original
2014
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…