Projective limits of probabilistic symmetries and their applications to random graph limits

This paper establishes a unified framework linking projective limits of probability measures to direct limits of their symmetry groups, demonstrating how this connection characterizes the symmetries of infinite point processes and provides a streamlined derivation of random graph limits, including graphons, graphexes, and models with bounded average degrees.

The Gist

Imagine you are trying to understand a massive, infinite city. You can't see the whole thing at once, so you start by looking at small neighborhoods, then larger districts, then entire boroughs. As you zoom out, you want to know: Does the pattern of the city stay consistent? And what are the "rules" that keep the city looking the same no matter how you rotate or rearrange it?

This paper is a mathematical guidebook for exactly that kind of problem, but instead of cities, it deals with random networks (like social networks, the internet, or neural connections) and the symmetries (the rules of rearrangement) that govern them.

Here is the breakdown in simple, everyday language:

1. The Core Idea: The "Zoom-Out" Machine

The authors are using two powerful mathematical tools that work in opposite directions:

• Projective Limits (The Zoom-Out): Imagine taking a photo of a small neighborhood, then a larger district, then the whole city. A "projective limit" is the mathematical way of stitching these photos together to create a perfect, infinite image of the whole city without losing any details. It asks: "If I have a consistent rule for how small pieces fit together, what does the infinite whole look like?"
• Direct Limits (The Rule-Book Upgrade): Now imagine you have a set of rules for rearranging the neighborhood (e.g., "swap house A and house B"). As you zoom out to the whole city, those rules need to get bigger. A "direct limit" is the process of upgrading your rulebook from "neighborhood rules" to "city-wide rules."

The Big Discovery: The authors proved that if you have a consistent way of zooming out (Projective Limit) and a consistent way of upgrading your rules (Direct Limit), the rules for the infinite city are exactly the upgraded version of the rules for the small neighborhoods.

In short: Symmetry is preserved when you zoom out. If a small graph looks the same when you swap two nodes, the giant infinite graph will look the same when you swap the corresponding infinite nodes.

2. The Application: Random Graphs as "Point Clouds"

To make this work, the authors treat edges (connections) in a graph as dots (points) in space.

• If you have a graph with people labeled 1 to 10, an edge between 1 and 2 is just a dot at coordinates (1, 2).
• As the graph grows, you are just adding more dots to a larger grid.

By treating graphs as clouds of points, they can use the "Zoom-Out" machine to see what happens when the graph becomes infinite.

3. Three Examples of "Infinite Cities"

The paper shows how this framework explains three different types of infinite networks, acting like a "shortest path" to understanding them:

A. The "Name-Tag" City (Graphons)

• The Setup: Imagine a city where everyone has a number tag (1, 2, 3...).
• The Rule: You can swap any two people's tags, and the city looks the same.
• The Result: When you zoom out to infinity, you get a Graphon. This is a famous mathematical object used to describe dense networks (like a crowded party where everyone knows everyone). It's like a smooth, blurry map of how likely any two people are to know each other.

B. The "Address" City (Graphexes)

• The Setup: Imagine a city where people live on a continuous line (like addresses on a street: 0.1, 0.5, 99.9...).
• The Rule: You can stretch or squish the street, as long as the "density" of people stays the same.
• The Result: When you zoom out, you get a Graphex. This describes sparse networks (like the internet or a social network where most people have few friends). It's a more complex map that handles the fact that connections are rare.

C. The "Orbital" City (The New Discovery)

• The Setup: Imagine a city in 3D space (like a galaxy). People are stars.
• The Rule: You can spin the whole galaxy around its center. The rules don't change if you rotate the view.
• The Result: This creates a new type of infinite network that is ultrasparse (very few connections, like the real world).
  • Why is this cool? Previous math tools couldn't handle these "ultrasparse" networks well. This new framework shows that if you build a network based on distance and rotation in space, you get a valid, predictable infinite limit.
  • Real-world use: This explains models used in quantum gravity (how space-time is built) and random geometric graphs (how sensors in a field connect).

4. Why This Matters

Before this paper, mathematicians had to invent different, complicated ways to study dense graphs, sparse graphs, and ultra-sparse graphs. It was like having three different languages to describe three types of cities.

This paper provides one universal grammar.

• It says: "If you define your network by how it grows and what symmetries it has, the infinite version is automatically defined by the 'limit' of those symmetries."
• It acts as a universal translator, allowing scientists to move easily between different types of random networks (from dense social webs to sparse cosmic structures) using the same logical framework.

The Takeaway

Think of this paper as a master key. It unlocks the door to understanding how finite, messy, small-world networks evolve into infinite, perfect structures. It proves that the "rules of the game" (symmetries) you play by in a small room are the exact same rules that govern the entire universe, provided you upgrade the rules correctly as you get bigger.

This allows researchers to finally study the "ultrasparse" networks that make up our real world (like the brain or the universe) with the same mathematical confidence they have had for dense networks for decades.

Technical Summary

Here is a detailed technical summary of the paper "Projective limits of probabilistic symmetries and their applications to random graph limits" by van der Hoorn, Stepanyants, and Krioukov.

1. Problem Statement

The paper addresses the challenge of rigorously defining and characterizing the limits of random graphs, particularly those that are ultrasparse (where the average degree remains bounded as the graph size $n \to \infty$).

• Context: Existing theories for graph limits are well-established for dense graphs (via graphons) and sparse graphs (via graphexes). However, these frameworks rely on specific symmetry groups (permutations of integers or measure-preserving transformations of reals) that do not naturally extend to the broad class of ultrasparse, rotationally invariant, or geometric random graphs found in many physical and biological networks.
• Gap: There is a lack of a unified framework that connects the limiting behavior of random graphs to their underlying symmetry groups, especially when the limit space is an infinite continuous domain (like $\mathbb{R}^d$) rather than a discrete set or a unit interval.
• Goal: To develop a general mathematical framework that couples the projective limits of probability measures (representing the random graphs) with the direct limits of their symmetry groups, thereby recovering known limits (graphons/graphexes) and establishing new limits for ultrasparse graphs.

2. Methodology

The authors employ tools from category theory, measure theory, and the theory of point processes. The core methodology involves:

A. Coupling Projective and Direct Limits

• Projective Limits (Inverse Limits): Used to construct the limit of a sequence of probability measures defined on increasing finite spaces. If $(X_n)$ is a sequence of spaces with projections $\pi_{mn}: X_m \to X_n$, the projective limit space $X_\infty$ contains sequences consistent with these projections.
• Direct Limits (Inductive Limits): Used to construct the limit of a sequence of symmetry groups $(\Phi_n)$ with embeddings $\eta_{nm}: \Phi_n \to \Phi_m$. The direct limit group $\Phi_\infty$ represents the "limit" of the symmetries.
• Compatibility: The authors define a compatible system where the group actions on the spaces commute with the projections. Specifically, acting on a set in a smaller space and then projecting is equivalent to projecting first and then acting in the larger space via the group embedding.

B. Point Process Representation

• Random graphs are modeled as point processes on a product space $L \times L$, where $L$ is the label space of vertices.
• An edge between vertices $x$ and $y$ is represented as a point $\{x, y\}$.
• The authors consider a projective system of point processes $(\mu_n)$ on increasing finite regions $X_n \subset X_\infty$ (where $X_\infty$ is an infinite Polish space).

C. Theoretical Framework

The paper establishes three main theorems:

1. Invariance Preservation: If a sequence of probability measures is invariant under a compatible direct system of groups, their projective limit is invariant under the direct limit of those groups.
2. Existence of Point Process Limits: Under specific topological conditions (exhausting sequences of open sets), the projective limit of point processes on finite subspaces exists and corresponds to a point process on the infinite space.
3. Extension to Larger Symmetry Groups: The authors introduce the concept of a compatible direct pre-limit. This allows the limit measure to be invariant under a larger group $\Phi_\infty$ (e.g., all permutations of $\mathbb{N}$) even if the direct limit of the finite groups $\Phi_n$ is only a dense subgroup (e.g., permutations of $\mathbb{N}$ with finite support).

3. Key Contributions

A. General Unified Framework

The paper provides a unified theoretical machinery to study limits of random graphs of varying densities (dense, sparse, and ultrasparse) by simply changing the label space $L$ and the symmetry group $\Phi$.

B. Recovery of Known Limits

The framework naturally recovers existing results as trivial corollaries:

• Graphons: By choosing $L = \mathbb{N}$ (integers) and $\Phi_n = S_n$ (symmetric group of permutations), the limit is a random graph on $\mathbb{N}$ invariant under infinite permutations. This recovers the Aldous-Hoover representation via graphons.
• Graphexes: By choosing $L = \mathbb{R}_+$ and $\Phi_n$ as measure-preserving transformations of $[0, n)$, the limit is a random graph on $\mathbb{R}_+$ invariant under measure-preserving transformations of $\mathbb{R}_+$. This recovers the graphex representation.

C. New Limits for Ultrasparse Graphs

The most significant contribution is the derivation of a new class of limits for ultrasparse graphs (bounded average degree).

• Setup: Label space $L = \mathbb{R}^d$ (Euclidean space). The finite regions $L_n$ are concentric balls of volume $n$.
• Symmetry: The symmetry group $\Phi_n$ is the group of rotations in $\mathbb{R}^d$ around the origin.
• Result: The projective limit yields a random graph on $\mathbb{R}^d$ that is rotationally invariant.
• Significance: Unlike graphons and graphexes, there is currently no known "nice" representation theorem (like a kernel function $W$) for these rotationally invariant limits. However, the framework proves their existence and invariance properties, encompassing models like:
  • Soft random geometric graphs.
  • Inhomogeneous random graphs.
  • Geometric inhomogeneous random graphs (hyperbolic graphs).
  • Causal sets in quantum gravity.

4. Key Results

1. Theorem 3.1 (Direct limit of compatible groups preserves invariance): Proves that probabilistic symmetries are preserved in the limit. If $\mu_n$ is $\Phi_n$-invariant, then $\mu_\infty = \lim \mu_n$ is $\Phi_\infty$-invariant.
2. Theorem 3.2 (Projective limits of point processes exist): Establishes that the projective limit of a system of point processes on expanding finite domains is a valid point process on the infinite domain.
3. Theorem 3.3 (Projective limits of invariant point processes are invariant): Extends invariance to the full symmetry group of the infinite space, not just the direct limit of the finite groups. This is crucial for showing that limits of graphs on $[0, n)$ are invariant under all measure-preserving transformations of $\mathbb{R}_+$, not just those with finite support.
4. Corollaries 4.3 & 4.4: Formalize the recovery of Graphons and Graphexes as specific instances of the general theory.
5. Section 4.3.3: Demonstrates that rotationally invariant point processes on $\mathbb{R}^d$ generate a vast class of ultrasparse random graphs, providing a rigorous foundation for models previously studied in isolation.

5. Significance

• Unification: The paper bridges the gap between dense and sparse graph limit theories, showing they are manifestations of the same underlying categorical structure (coupling projective limits of measures with direct limits of groups).
• "Shortest Paths" to Limits: The authors argue that their approach provides a "shortest path" to deriving graphons and graphexes, bypassing complex combinatorial arguments by relying on general measure-theoretic principles.
• New Research Directions: By formalizing the limit of rotationally invariant graphs, the paper opens the door to developing representation theorems for ultrasparse networks. This is critical for fields like network science, statistical physics, and quantum gravity, where real-world networks are often ultrasparse and possess geometric symmetries that standard graphon theory cannot capture.
• Generalizability: The framework is not limited to graphs; it applies to any point process where the underlying space and symmetry groups can be defined as compatible projective/direct systems.

In summary, the paper establishes a robust mathematical foundation for the limits of random graphs, successfully unifying existing theories and providing a pathway to analyze complex, ultrasparse, and geometrically structured networks that were previously outside the scope of standard limit theories.