Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 32146
The Giant Component in a Random Subgraph of a Weak Expander

Authors: Yilun Shang


In this paper, we investigate the appearance of the giant component in random subgraphs G(p) of a given large finite graph family Gn = (Vn, En) in which each edge is present independently with probability p. We show that if the graph Gn satisfies a weak isoperimetric inequality and has bounded degree, then the probability p under which G(p) has a giant component of linear order with some constant probability is bounded away from zero and one. In addition, we prove the probability of abnormally large order of the giant component decays exponentially. When a contact graph is modeled as Gn, our result is of special interest in the study of the spread of infectious diseases or the identification of community in various social networks.

Keywords: subgraph, expander, random graph, giant component, percolation.

Digital Object Identifier (DOI):

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1560


[1] N. Alon, I. Benjamini and A. Stacey, Percolation on finite graphs and isoperimetric inequalities. Ann. Probab., 32(2004) 1727-1745.
[2] N. Alon, J. Bruck, J. Naor, M. Naor and R. M. Roth, Construcction of asymptotically good low-rate error-correcting codes through pseudo- random graphs. IEEE TransactionS ON ıNFORMATİON tHEORY, 38(1992) 509- 516.
[3] I. Benjamini, S. Boucheron, G. Lugosi and R. Rossignol, Sharp treshold for percolation on expanders. arXiv:0906.3657.
[4] I. Benjamini and O. Schramm, Percolation beyond Zd, many questions and a few answers. Electron. Comm. Probab., 1(1996) 71-82.
[5] S. Ben-Shimon and M. Krivelevich, Vertex percolation on expander graphs. European J. Combin., 30(2009) 339-350.
[6] B. Bollobás, Random Graphs. Cmabridge University Press, Cmabridge, 2001.
[7] F. Chung, P. Horn and L. Lu, Percolation in general graphs. Internet Math., 6(2009) 331-347.
[8] F. Chung and L. Lu, Complex Graphs and Networks. AMS Publications, 2006.
[9] P. Flajolet and R. Sedgewick, Analytic Combinatorics. Cambridge Uni- versity Press, Cambridge, 2009.
[10] C. Greenhill, F. B. Holt and N. Wormald, Expansion properties of a random regular graph after random vertex deletions. European J. Combin., 29(2008) 1139-1150.
[11] S. Janson, Large deviations for sums of partly dependent random variales. Random Struct. Alg., 24(2004) 234-248.
[12] S. Janson, T. Łuczak and A. Rucinski, Random Graphs. Wiley, New York, 2000.
[13] R. Lyons, Phase transtions on nonamenable graphs, J. Math. Phys., 41(2000) 1099-1126.
[14] R. Lyons and Y. Peres, Probability on Trees and Networks. Cam- bridge University Press, in preparation, current version available at
[15] A. Nachmias and Y. Peres, Critical percolation on random regular graphs. Random Struct. Alg., 36(2000) 111-148.
[16] B. Pittel, Edge percolation on a random regular graph of low degree. Ann. Probab., 36(2008) 1359-1389.