An elementary approach to component sizes in critical random graphs. (English) Zbl 1503.05109
Summary: In this article we introduce a simple tool to derive polynomial upper bounds for the probability of observing unusually large maximal components in some models of random graphs when considered at criticality. Specifically, we apply our method to a model of a random intersection graph, a random graph obtained through \(p\)-bond percolation on a general \(d\)-regular graph, and a model of an inhomogeneous random graph.
MSC:
| 05C80 | Random graphs (graph-theoretic aspects) |
| 05C81 | Random walks on graphs |
| 60G50 | Sums of independent random variables; random walks |
| 60C05 | Combinatorial probability |
References:
| [1] | Addario-Berry, L. and Reed, B. A. (2008). Ballot theorems, old and new. In Horizons of Combinatorics (Bolyai Society Mathematical Studies 17), pp. 9-35. Springer, Berlin and Heidelberg. · Zbl 1151.91412 |
| [2] | Behrisch, M. (2007). Component evolution in random intersection graphs. Electron. J. Combin.14, R17. · Zbl 1114.05093 |
| [3] | Bollobás, B. (2001). Random Graphs, 2nd edn. Cambridge University Press, Cambridge. · Zbl 0979.05003 |
| [4] | Bollobás, B., Janson, S. and Riordan, O. (2007). The phase transition in inhomogeneous random graphs. Random Structures Algorithms31, 3-122. · Zbl 1123.05083 |
| [5] | Chung, F. and Lu, L. (2002). Connected components in random graphs with given expected degree sequences. Ann. Combinatorics6, 125-145. · Zbl 1009.05124 |
| [6] | Chung, F. and Lu, L. (2003). The average distance in a random graph with given expected degrees. Internet Math.1, 91-113. · Zbl 1065.05084 |
| [7] | Chung, F. and Lu, L. (2006). The volume of the giant component of a random graph with given expected degrees. SIAM J. Discrete Math.20, 395-411. · Zbl 1119.05098 |
| [8] | De Ambroggio, U. and Pachon, A. (2020). Simple upper bounds for the largest components in critical inhomogeneous random graphs. Available at arXiv:2012.09001. |
| [9] | De Ambroggio, U. and Roberts, M. I. (2021). Unusually large components in near-critical Erdős-Rényi graphs via ballot theorems. Available at arXiv:2101.05358. |
| [10] | Deijfen, M. and Kets, W. (2009). Random intersection graphs with tunable degree distribution and clustering. Prob. Eng. Inf. Sci.23, 661-674. · Zbl 1180.68212 |
| [11] | Frieze, A. and Karoński, M. (2015). Introduction to Random Graphs. Cambridge University Press, Cambridge. |
| [12] | Van Der Hofstad, R. (2013). Critical behaviour in inhomogeneous random graphs. Random Structures Algorithms42, 480-508. · Zbl 1269.05101 |
| [13] | Van Der Hofstad, R. (2016). Random Graphs and Complex Networks, Vol. 1 (Cambridge Series in Statistical and Probabilistic Mathematics43). Cambridge University Press, Cambridge. |
| [14] | Janson, S. (2009). Asymptotic equivalence and contiguity of some random graphs. Random Structures Algorithms36, 26-45. · Zbl 1209.05225 |
| [15] | Janson, S., Łuczak, T. and Ruciński, A. (2011). Random Graphs. John Wiley, New York. |
| [16] | Joos, F. and Perarnau, G. (2018). Critical percolation on random regular graphs. Proc. Amer. Math. Soc. 146, 3321-3332. · Zbl 1388.05170 |
| [17] | Kager, W. (2011). The hitting time theorem revisited. Amer. Math. Monthly118, 735-737. · Zbl 1229.60053 |
| [18] | Kang, M., Pachon, A. and Rodriguez, P. M. (2018). Evolution of a modified binomial random graph by agglomeration. J. Statist. Phys.170, 509-535. · Zbl 1386.05177 |
| [19] | Krivelevich, M. and Sudakov, B. (2012). The phase transition in random graphs: a simple proof. Random Structures Algorithms43, 131-138. · Zbl 1272.05181 |
| [20] | Lageras, A. N. and Lindholm, M. (2008). A note on the component structure in random intersection graphs with tunable clustering. Electron. J. Combin.15, N10. · Zbl 1160.05335 |
| [21] | Łuczak, T., Pittel, B. and Wierman, J. C. (1994). The structure of a random graph at the point of the phase transition. Trans. Amer. Math. Soc.341, 721-748. · Zbl 0807.05065 |
| [22] | Nachmias, A. and Peres, Y. (2010). Critical percolation on random regular graphs. Random Structures Algorithms36, 111-148. · Zbl 1209.05228 |
| [23] | Nachmias, A. and Peres, Y. (2010). The critical random graph, with martingales. Israel J. Math.176, 29-41. · Zbl 1215.05168 |
| [24] | Norros, I. and Reittu, H. (2006). On a conditionally Poissonian graph process. Adv. Appl. Prob.38, 59-75. · Zbl 1096.05047 |
| [25] | Penrose, M. D. (2018). Inhomogeneous random graphs, isolated vertices, and Poisson approximation. J. Appl. Prob.55, 112-136. · Zbl 1396.05102 |
| [26] | Pittel, B. (2001). On the largest component of the random graph at a nearcritical stage. J. Combinatorial Theory B82, 237-269. · Zbl 1028.05102 |
| [27] | Roberts, M. I. (2017). The probability of unusually large components in the near-critical Erdős-Rényi graph. Adv. Appl. Prob.50, 245-271. · Zbl 1431.60009 |
| [28] | Stark, D. (2004). The vertex degree distribution of random intersection graphs. Random Structures Algorithms24, 249-258. · Zbl 1042.05091 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
