Limit theorems for walks and triangles on Erdös-Rényi random graphs with large interaction radius

This paper establishes limit theorems for the number of walks and triangles in Erdős-Rényi random graphs with large interaction radii by deriving cumulant expansions associated with tree-type diagrams, identifying a threshold between normal and Poisson distributions for triangles, and demonstrating that the total number of triangles can grow infinitely while the average vertex degree remains bounded.

The Gist

The Big Picture: Mapping a Shifting City

Imagine you are an urban planner trying to understand the traffic flow in a giant, ever-expanding city. In this city, the "roads" are connections between people (or nodes), and the "traffic" is the movement of information or energy along these roads.

Usually, mathematicians study a city where every person has an equal chance of knowing every other person, regardless of distance. This is the classic Erdős-Rényi model. But in this paper, the author, O. Khorunzhiy, studies a more realistic city: The Distance-Dependent City.

In this city, you are much more likely to have a road connecting you to your neighbor than to someone living on the other side of the world. The "interaction radius" ($R$) is like the size of your neighborhood. If $R$ is small, you only know your immediate neighbors. If $R$ is huge, you know people across the whole city.

The paper asks: What happens to the traffic patterns when the city gets infinitely large, the number of people grows, and the neighborhood size ($R$) also grows?

The Three Scenarios (Asymptotic Regimes)

The author discovers that the behavior of this city changes drastically depending on the relationship between the city size ($N$), the population density ($c$), and the neighborhood size ($R$). He identifies three distinct "weather patterns" or regimes:

1. The Dense Fog (High Concentration): Here, the neighborhood is so large and the population so dense that everyone is effectively connected to everyone else. It's like a crowded room where you can hear everyone talking.
2. The Balanced Neighborhood (Medium Concentration): The neighborhood size and population are perfectly balanced. You have a stable number of connections, neither too sparse nor too crowded.
3. The Sparse Desert (Low Concentration): The neighborhood is huge, but the population is spread so thin that connections are rare. It's like a vast desert where you might only see a few other people for miles.

The Two Main Measurements

To understand the city, the author counts two specific things:

1. The Walks (Open Paths): Imagine a traveler taking $q$ steps through the city, starting at one house and ending at a different one. The author counts how many unique paths of this length exist.

   • The Finding: In all three regimes, the number of these walks follows a predictable pattern (a "Normal Distribution," like a bell curve). It's as if the chaos of the city averages out into a smooth, predictable flow.

2. The Triangles (Closed Loops): Imagine a traveler starting at a house, visiting two others, and returning to the start. This forms a triangle. In graph theory, these are called "triangles."

   • The Finding: This is where it gets tricky.
     • In the Dense and Balanced regimes, the number of triangles also follows a smooth, predictable bell curve.
     • However, in the Sparse regime, something magical happens. If the parameters are just right, the number of triangles doesn't follow a bell curve; it follows a Poisson Distribution.
     • The Analogy: Think of the bell curve as a steady stream of rain (predictable, constant). The Poisson distribution is like lightning strikes. You know lightning happens, but you can't predict exactly when the next one will strike. It's rare, random, and "spiky."

The "Graph Collapse" Problem Solved

One of the most exciting claims in the paper is solving a problem known as "Graph Collapse."

• The Problem: Usually, if you want a city to have a massive number of triangles (tight-knit groups of three friends), you need to pack the city so tightly that the average person has thousands of friends. This makes the graph "collapse" into a chaotic mess where the structure breaks down.
• The Solution: The author shows that by using this "Distance-Dependent" model with a large interaction radius, you can have a city where:
  1. The average number of friends per person stays low and manageable (finite).
  2. The total number of triangles (tight-knit groups) grows infinitely large.

The Metaphor: Imagine a party. Usually, if you want millions of three-person conversations happening, you need a stadium packed shoulder-to-shoulder. The author shows you can have a massive number of these conversations even if everyone is standing far apart, provided the "room" (the interaction radius) is shaped just right. The structure holds together without collapsing.

The "Tree" Analogy for the Math

To prove these results, the author uses a technique called Diagrammatics. He translates the complex math of random graphs into pictures of trees.

• Imagine the connections in the city as branches.
• He classifies these branches into "Maximal Trees" (big, sprawling branches), "Minimal Trees" (tiny twigs), and everything in between.
• He uses a coding system called Prüfer Codification (a way of turning a tree into a unique string of numbers, like a barcode) to count exactly how many of these tree structures exist.
• By counting these "tree barcodes," he can calculate the exact probability of the city behaving in a certain way.

Summary of the "Limit Theorems"

The paper proves that as the city grows to infinity:

• Open Walks: Always behave like a smooth, predictable bell curve.
• Triangles: Can behave like a bell curve OR like random lightning strikes (Poisson), depending on how the city is built.
• The "Collapse": It is mathematically possible to have a huge, complex network of tight-knit groups (triangles) without the network becoming so dense that it breaks.

In short, the author has mapped the "physics" of a giant, distance-sensitive network, showing us exactly when it behaves smoothly and when it behaves like a series of random, rare events, and proving that we can build complex structures without causing a collapse.

Technical Summary

Technical Summary: Limit Theorems for Walks and Triangles on Erdős-Rényi Random Graphs with Large Interaction Radius

Problem Statement
The paper investigates the asymptotic behavior of cumulants associated with the number of $q$-step walks and the number of triangles (3-step closed walks) on a modified ensemble of Erdős-Rényi random graphs. Unlike the classical Erdős-Rényi model where edge probabilities are uniform, this study considers graphs where the edge probability depends on the distance between vertices, governed by an interaction radius $R$. The analysis focuses on the limit where the number of vertices $N$, the concentration parameter $c$, and the interaction radius $R$ tend to infinity simultaneously.

The primary objective is to characterize the limiting distributions of these subgraph counts under three distinct asymptotic regimes defined by the scaling of the parameters $cR/N$ (for non-closed walks) and $c^2R/N^2$ (for triangles). A specific motivation is to resolve the "graph collapse problem," a phenomenon where the total number of triangles might diverge while the average vertex degree remains bounded, a scenario not possible in standard Erdős-Rényi ensembles.

Methodology
The authors employ a combination of random matrix theory techniques and combinatorial diagram methods. The core methodology involves:

1. Cumulant Expansion: The study utilizes the cumulant expansion of the free energy of matrix models. The random variables of interest, $Y^{(q)}$ (total non-closed walks) and $X^{(q)}$ (total closed walks), are expressed via traces of powers of the adjacency matrix.
2. Diagram Technique: The authors adapt a diagrammatic approach (connected diagrams) to compute the mixed cumulants of these variables. They represent the product of random variables as multi-graphs constructed from linear elements ($\lambda_q$ for walks) or triangle elements ($\mu_3$ for triangles).
3. Classification of Diagrams: The diagrams are classified into three types based on their topological structure:
   • Maximal tree-type diagrams: Those with the maximum number of edges for a given number of vertices.
   • General tree-type diagrams: All diagrams forming a tree structure.
   • Minimal tree-type diagrams: Those with the minimum number of edges (often single edges with high multiplicity).
4. Asymptotic Analysis: By analyzing the order of magnitude of the weights associated with these diagrams in the limit $N, c, R \to \infty$, the authors determine which class of diagrams dominates the cumulant expansion in each of the three regimes.
5. Combinatorial Enumeration: To derive explicit expressions for the limiting cumulants, the paper utilizes a modified Prüfer codification procedure (color Prüfer codes) to enumerate the number of maximal and minimal tree-type diagrams.

Key Results

1. Limiting Cumulants for Non-Closed Walks ($Y^{(q)}$):
   The paper establishes the existence of limiting values for the $k$-th cumulants of $Y^{(q)}$ in three regimes determined by the ratio $cR/N$:

   • Dense Regime ($cR/N \gg 1$): The limiting cumulants are determined by the number of maximal tree-type diagrams.
   • Intermediate Regime ($cR/N = s$): The limiting cumulants are determined by the sum over all tree-type diagrams.
   • Sparse Regime ($cR/N \ll 1$): The limiting cumulants are determined by minimal tree-type diagrams.
     Explicit formulas are provided for these limits, involving integrals of the interaction function $\psi(x)$ and combinatorial factors derived from the Prüfer code enumeration.

2. Limiting Cumulants for Triangles ($X^{(3)}$):
   Similar results are derived for the number of triangles, governed by the parameter $c^2R/N^2$:

   • In the dense and intermediate regimes, the limits correspond to maximal and general tree-type diagrams, respectively.
   • In the sparse regime ($c^2R/N^2 \ll 1$), the limits are determined by minimal diagrams, leading to expressions involving the Fourier transform of the interaction kernel.

3. Limit Theorems (Distributional Convergence):

   • Central Limit Theorem (CLT): For non-closed walks ($Y^{(q)}$), the normalized variables converge to a Gaussian distribution in all three regimes. For triangles ($X^{(3)}$), the CLT holds in the first two regimes and in the third regime only if the average number of triangles ($c^3R^2/N^2$) tends to infinity.
   • Poisson Limit: In the specific regime where $c^2R/N^2 \to 0$ but $c^3R^2/N^2 \to \Lambda$ (finite), the number of triangles converges to a Poisson distribution (or a compound Poisson distribution if $\alpha=1$). This identifies an asymptotic threshold separating Gaussian and Poisson behaviors.

4. Resolution of the Graph Collapse Problem:
   The paper rigorously demonstrates the existence of an asymptotic regime where the average vertex degree remains finite (bounded), yet the total number of triangles increases infinitely. Specifically, by choosing sequences where $cR/N \to \delta$ (finite) and $c^3R^2/N^2 \to \infty$, the authors prove that the graph does not "collapse" in the sense of losing structure; rather, it supports an infinite number of triangles while maintaining a bounded local density.

Significance and Claims
The paper claims to provide a rigorous mathematical framework for understanding random graphs with distance-dependent edge probabilities, generalizing the classical Erdős-Rényi model. The significance lies in:

• Generalization: Extending limit theorems from uniform random graphs to those with interaction radii, bridging the gap between random matrix theory and geometric random graphs.
• Phase Transition Analysis: Identifying precise asymptotic thresholds that dictate whether subgraph counts follow Gaussian or Poisson laws, and determining the analyticity of the free energy for exponential random graph models.
• Solving the Collapse Problem: Providing a constructive proof that the "collapse" of the graph (where triangles vanish or degrees become unbounded) is not inevitable; one can construct ensembles with bounded degrees and diverging triangle counts, solving a problem known in applications.
• Combinatorial Insight: Offering explicit enumerations of tree-type diagrams via modified Prüfer codes, which yield exact expressions for the limiting cumulants.

The authors conclude that these results allow for a precise characterization of the free energy of matrix models associated with these random graphs, indicating the presence or absence of phase transitions depending on the sparsity of the graph and the strength of the interaction.