Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-29T07:55:30.740Z Has data issue: false hasContentIssue false
  • English
  • Français

An elementary approach to component sizes in critical random graphs

Part of: Stochastic processes Graph theory Combinatorial probability

Published online by Cambridge University Press:  11 November 2022

Umberto De Ambroggio Open the ORCID record for Umberto De Ambroggio [Opens in a new window]
Umberto De Ambroggio*
Affiliation:
University of Bath
*
*Postal address: Department of Mathematical Sciences, University of Bath, Bath BA2 7AY, UK. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

Keywords

Random walkballot theorem

MSC classification

Primary: 05C80: Random graphs
Secondary: 60G50: Sums of independent random variables; random walks 60C05: Combinatorial probability
Type
Original Article
Information
Journal of Applied Probability , Volume 59 , Issue 4 , December 2022 , pp. 1228 - 1242
Check for updates
Copyright
© The Author(s), 2022. Published by Cambridge University Press on behalf of Applied Probability Trust

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

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.CrossRefGoogle Scholar
Behrisch, M. (2007). Component evolution in random intersection graphs. Electron. J. Combin. 14, R17.CrossRefGoogle Scholar
Bollobás, B. (2001). Random Graphs, 2nd edn. Cambridge University Press, Cambridge.CrossRefGoogle Scholar
Bollobás, B., Janson, S. and Riordan, O. (2007). The phase transition in inhomogeneous random graphs. Random Structures Algorithms 31, 3–122.CrossRefGoogle Scholar
Chung, F. and Lu, L. (2002). Connected components in random graphs with given expected degree sequences. Ann. Combinatorics 6, 125–145.CrossRefGoogle Scholar
Chung, F. and Lu, L. (2003). The average distance in a random graph with given expected degrees. Internet Math. 1, 91–113.CrossRefGoogle Scholar
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.CrossRefGoogle Scholar
De Ambroggio, U. and Pachon, A. (2020). Simple upper bounds for the largest components in critical inhomogeneous random graphs. Available at arXiv:2012.09001.Google Scholar
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.Google Scholar
Deijfen, M. and Kets, W. (2009). Random intersection graphs with tunable degree distribution and clustering. Prob. Eng. Inf. Sci. 23, 661–674.Google Scholar
Frieze, A. and Karoński, M. (2015). Introduction to Random Graphs. Cambridge University Press, Cambridge.CrossRefGoogle Scholar
van der Hofstad, R. (2013). Critical behaviour in inhomogeneous random graphs. Random Structures Algorithms 42, 480–508.CrossRefGoogle Scholar
van der Hofstad, R. (2016). Random Graphs and Complex Networks, Vol. 1 (Cambridge Series in Statistical and Probabilistic Mathematics 43). Cambridge University Press, Cambridge.CrossRefGoogle Scholar
Janson, S. (2009). Asymptotic equivalence and contiguity of some random graphs. Random Structures Algorithms 36, 26–45.Google Scholar
Janson, S., Łuczak, T. and Ruciński, A. (2011). Random Graphs. John Wiley, New York.Google Scholar
Joos, F. and Perarnau, G. (2018). Critical percolation on random regular graphs. Proc. Amer. Math. Soc. 146, 3321–3332.CrossRefGoogle Scholar
Kager, W. (2011). The hitting time theorem revisited. Amer. Math. Monthly 118, 735–737.CrossRefGoogle Scholar
Kang, M., Pachon, A. and Rodriguez, P. M. (2018). Evolution of a modified binomial random graph by agglomeration. J. Statist. Phys. 170, 509–535.CrossRefGoogle Scholar
Krivelevich, M. and Sudakov, B. (2012). The phase transition in random graphs: a simple proof. Random Structures Algorithms 43, 131–138.CrossRefGoogle Scholar
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.CrossRefGoogle Scholar
Ł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.CrossRefGoogle Scholar
Nachmias, A. and Peres, Y. (2010). Critical percolation on random regular graphs. Random Structures Algorithms 36, 111–148.Google Scholar
Nachmias, A. and Peres, Y. (2010). The critical random graph, with martingales. Israel J. Math. 176, 29–41.CrossRefGoogle Scholar
Norros, I. and Reittu, H. (2006). On a conditionally Poissonian graph process. Adv. Appl. Prob. 38, 59–75.CrossRefGoogle Scholar
Penrose, M. D. (2018). Inhomogeneous random graphs, isolated vertices, and Poisson approximation. J. Appl. Prob. 55, 112–136.CrossRefGoogle Scholar
Pittel, B. (2001). On the largest component of the random graph at a nearcritical stage. J. Combinatorial Theory B 82, 237–269.CrossRefGoogle Scholar
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.Google Scholar
Stark, D. (2004). The vertex degree distribution of random intersection graphs. Random Structures Algorithms 24, 249–258.CrossRefGoogle Scholar