Begin your search of the AGOSR Open Access Database
Cover Image for System.Linq.Enumerable+EnumerablePartition`1[System.Char]

Unusually large components in near-critical Erdös-Rényi graphs via ballot theorems

OAI: oai:purehost.bath.ac.uk:openaire_cris_publications/963ba2ad-a47e-4e42-a6e6-b9b76829fcf8 • DOI: https://doi.org/10.1017/S0963548321000584
Published by:

Abstract

We consider the near-critical Erdos-Rényi random graph G(n, p) and provide a new probabilistic proof of the fact that, when p is of the form p=p(n)=1/n+λ/n4/3 and A is large, {equation presented} where Cmax is the largest connected component of the graph. Our result allows A and λ to depend on n. While this result is already known, our proof relies only on conceptual and adaptable tools such as ballot theorems, whereas the existing proof relies on a combinatorial formula specific to Erdos-Rényi graphs, together with analytic estimates.