The Giant Component in a Random Subgraph of a Weak Expander

Authors: Yilun Shang

Abstract:

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): doi.org/10.5281/zenodo.1071045

References:

[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 http://mypage.iu.edu/~rdlyons/.
[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.