Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-13T22:07:06.503Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Expansion of the Giant Component in Percolated (n, d,λ) Graphs

Published online by Cambridge University Press:  01 May 2007

ERAN OFEK
ERAN OFEK*
Affiliation:
Department of Computer Science and Applied Mathematics, Weizmann Institute, Rehovot 76100, Israel (e-mail: eran.ofek@weizmann.ac.il)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let d ≥ d0 be a sufficiently large constant. An $(n, d, c \sqrt{d})$ graph G is a d-regular graph over n vertices whose second-largest (in absolute value) eigenvalue is at most $c \sqrt{d}$. For any 0<p<1, Gp is the graph induced by retaining each edge of G with probability p. It is known that for $p>\frac{1}{d}$ the graph Gp almost surely contains a unique giant component (a connected component with linear number vertices). We show that for $p \geq \frac{5c}{\sqrt{d}}$ the giant component of Gp almost surely has an edge expansion of at least $\frac{1}{\log n}$.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 16 , Issue 3 , May 2007, pp. 445 - 457
Copyright
Copyright © Cambridge University Press 2006

References

[1]Alon, N. (1986) Eigenvalues and expanders. Combinatorica 6 83–96.CrossRefGoogle Scholar
[2]Alon, N., Benjamini, I. and Stacey, A. (2004) Percolation on finite graphs and isoperimetric inequalities. Ann. Probab. 32 1727–1745.CrossRefGoogle Scholar
[3]Alon, N. and Chung, F. R. K. (1988) Explicit construction of linear sized tolerant networks. Discrete Math. 72 15–19.CrossRefGoogle Scholar
[4]Alon, N. and Kahale, N. (1997) A spectral technique for coloring random 3-colorable graphs. SIAM J. Comput. 26 1733–1748.CrossRefGoogle Scholar
[5]Alon, N. and Milman, V. D. (1985) λ1, isoperimetric inequalities for graphs and superconcentrators. J. Combin. Theory Ser. B 38 73–88.CrossRefGoogle Scholar
[6]Alon, N. and Spencer, J. (2000) The Probabilistic Method, Wiley.CrossRefGoogle Scholar
[7]Bagchi, A., Bhargava, A., Chaudhary, A., Eppstein, D. and Scheideler, C. (2004) The effect of faults on network expansion. In SPAA 2004, pp. 286–293.Google Scholar
[8]Benjamini, I. and Schramm, O. (1996) Percolation beyond ${\mathbb Z}_d$, many questions and a few answers. Electron. Commun. Probab. 1 71–82.CrossRefGoogle Scholar
[9]Bilu, Y. and Linial, N. (2004) Lifts, discrepancy and nearly optimal spectral gaps. In FOCS 2004, pp. 404–412.Google Scholar
[10]Chen, H. and Frieze, A. (1996) Coloring bipartite hypergraphs. In IPCO 1996, pp. 345–358.Google Scholar
[11]Coja-Oghlan, A. (2005) A spectral heuristic for bisecting random graphs. In SODA 2005, pp. 850–859.Google Scholar
[12]Flaxman, A. (2003) A spectral technique for random satisfiable 3CNF formulas. In SODA 2003, pp. 357–363.Google Scholar
[13]Frieze, A., Krivelevich, M. and Martin, R. (2004) Emergence of a giant component in random subgraphs of pseudo-random graphs. Random Struct. Alg. 24 42–50.CrossRefGoogle Scholar
[14]Goerdt, A. and Lanka, A. (2004) On the hardness and easiness of random 4-sat formulas. In ISAAC 2004, pp. 470–483.Google Scholar
[15]Impagliazzo, R., Nisan, N. and Wigderson, A. (1994) Pseudorandomness for network algorithms. In STOC 1994, pp. 356–364.Google Scholar
[16]Kahale, N. (1995) Eigenvalues and expansion of regular graphs. J. Assoc. Comput. Mach. 42 1091–1106.CrossRefGoogle Scholar
[17]Lubotzky, A., Phillips, R. and Sarnak, P. (1988) Ramanujan graphs. Combinatorica 8 261–277.CrossRefGoogle Scholar
[18]Margulis, G. A. (1973/1975) Explicit constructions of concentrators. Problemy Peredači Informacii 9 71–80 (1973). English translation in Problems of Information Transmission pp. 325–332.Google Scholar
[19]Pak, I. and Smirnova-Nagnibeda, T. (2000) Uniqueness of percolation on nonamenable Cayley graphs. CR Acad. Sci. Paris Ser. I: Math. 330 495–500.CrossRefGoogle Scholar
[20]Reingold, O. (2005) Undirected ST-connectivity in logspace. In STOC 2005, pp. 376–385.Google Scholar
[21]Reingold, O., Vadhan, S. and Wigderson, A. (2002) Entropy waves, the zig-zag graph product and new constant-degree expanders. Ann. of Math. 155 157–187.CrossRefGoogle Scholar
[22]Sipser, M. and Spielman, D. A. (1996) Expander codes. IEEE Trans. Inform. Theory 42 1710–1722.CrossRefGoogle Scholar
[23]Tanner, R. M. (1984) Explicit construction of concentrators from generalized $n-gons. SIAM J. Algebraic Discrete Methods 5 287–294.CrossRefGoogle Scholar
[24]Upfal, E. (1992) Tolerating linear number of faults in networks of bounded degree. In PODC 1992, pp. 83–89.Google Scholar