No CrossRef data available.
Article contents
On the Expansion of the Giant Component in Percolated (n, d,λ) Graphs
Published online by Cambridge University Press: 01 May 2007
Abstract
Let d ≥ d0 be a sufficiently large constant. An graph G is a d-regular graph over n vertices whose second-largest (in absolute value) eigenvalue is at most . For any 0<p<1, Gp is the graph induced by retaining each edge of G with probability p. It is known that for the graph Gp almost surely contains a unique giant component (a connected component with linear number vertices). We show that for the giant component of Gp almost surely has an edge expansion of at least .
- Type
- Paper
- Information
- Copyright
- Copyright © Cambridge University Press 2006
References
[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
[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 , 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