2021•arXiv (Cornell University)Open access

The giant in random graphs is almost local

Remco van der Hofstad

Open full text 0 citations

Abstract

Local convergence techniques have become a key methodology to study sparse random graphs. However, convergence of many random graph properties does not directly follow from local convergence. A notable, and important, such random graph property is the size and uniqueness of the giant component. We provide a simple criterion that guarantees that local convergence of a random graph implies the convergence of the proportion of vertices in the maximal connected component. We further show that, when this condition holds, the local properties of the giant, as well as its complement, are also described by the local limit. We give several examples where this method gives rise to a novel law of large numbers for the giant, based on results proved in the literature. Aside from these examples, we apply our method to the classical problem of giants in the configuration model as a proof of concept, reproving a well-established result. As a side result of this proof, we give an extremely simple proof of the small-world nature of the configuration model.

Open-access reader

About this research paper

What this paper is about

Local convergence techniques have become a key methodology to study sparse random graphs. However, convergence of many random graph properties does not directly follow from local convergence. A notable, and important, such random graph property is the size and uniqueness of the giant component. We provide a simple criterion that guarantees that local convergence of a random graph implies the convergence of the proportion of vertices in the maximal connected component. We further show that, when this condition holds, the local properties of the giant, as well as its complement, are also described by the local limit. We give several examples where this method gives rise to a novel law of large numbers for the giant, based on results proved in the literature. Aside from these examples, we apply our method to the classical problem of giants in the configuration model as a proof of concept, reproving a well-established result. As a side result of this proof, we give an extremely simple proof of the small-world nature of the configuration model.

Why it matters

A significance statement is not available in the OpenAlex record.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

Local convergence techniques have become a key methodology to study sparse random graphs. However, convergence of many random graph properties does not directly follow from local convergence. A notable, and important, such random graph property is the size and uniqueness of the giant component. We provide a simple criterion that guarantees that local convergence of a random graph implies the convergence of the proportion of vertices in the maximal connected component. We further show that, when this condition holds, the local properties of the giant, as well as its complement, are also described by the local limit. We give several examples where this method gives rise to a novel law of large numbers for the giant, based on results proved in the literature. Aside from these examples, we apply our method to the classical problem of giants in the configuration model as a proof of concept, reproving a well-established result. As a side result of this proof, we give an extremely simple proof of the small-world nature of the configuration model.

Key concepts: Giant component, Random graph, Mathematics, Uniqueness, Random geometric graph, Bounded function, Convergence (economics), Combinatorics

Related papers

Back to paper searchBrowse research topicsOriginal source
The giant in random graphs is almost local — Research Paper | ScholarLens