Optimal graphons in the edge-2star model

Imagine you are a city planner trying to design a massive, bustling metropolis. You have two strict rules for how the city must look:

The Traffic Rule: Exactly half of all possible roads between any two buildings must exist (this is the "edge density").
The Hub Rule: You want a specific amount of "hubs"—places where three buildings are connected in a "V" shape (two roads meeting at a central building). This is the "2-star density."

Your goal is to build the city that is the most "chaotic" or "random" possible while still obeying these two rules. In the world of mathematics, this chaos is called entropy. The more random a city looks, the higher its entropy. The "optimal graphon" is the blueprint for the most random city that fits your rules.

This paper by Radin and Sadun explores what happens when you tweak these rules, specifically looking at the moment when the city tries to decide between two very different architectural styles.

The Two Architectural Styles: The Clique and the Anti-Clique

The authors discover that depending on how you set your rules, the most random city will naturally fall into one of two distinct shapes:

The "Clique" Style: Imagine a city where a specific group of buildings forms a tight-knit, super-connected neighborhood (everyone knows everyone), while the rest of the city is a ghost town with almost no connections.
The "Anti-Clique" Style: Imagine the opposite. The city has a large, empty, disconnected zone in the middle, but the buildings outside that zone are all tightly connected to each other.

The Great Divide (The Phase Transition)

The paper's main discovery is about a "tipping point" in the rules.

Imagine you are walking along a path where the "Traffic Rule" is fixed at exactly 50% (half the roads exist). As you walk, you slowly increase the "Hub Rule" (demanding more V-shaped connections).

On the Left Side: If you demand just a little more hubs, the city settles into a unique, stable shape. It's a balanced, symmetrical city.
On the Right Side: If you demand a lot of hubs, the city suddenly snaps into one of two extreme shapes: either the "Clique" style or the "Anti-Clique" style.

Here is the twist: At the exact middle point, the city is confused. It doesn't know which style to pick. There are two equally perfect blueprints (one Clique, one Anti-Clique) that are both the most random possible. The city has to "choose" one, and the choice is arbitrary. This is what the authors call a discontinuous phase transition. It's like water freezing into ice; at the exact freezing point, it can be liquid or solid, but the moment you cross the line, it snaps into one state.

The "Smooth" Zone vs. The "Jagged" Zone

The authors map out the entire landscape of possibilities:

The Smooth Zone (Near the bottom): When the rules are close to a standard, boring random city (where connections are spread out evenly), there is only one best blueprint. As you tweak the rules slightly, the blueprint changes smoothly, like stretching a rubber band. There are no sudden jumps.
The Jagged Zone (Near the top): When you push the rules to the extreme (demanding maximum hubs), the city becomes unstable. You get that split between the Clique and Anti-Clique styles. If you cross the line between them, the city's structure changes abruptly.

The "Symmetry Breaking" Moment

The paper also investigates the exact moment when the city stops being a "symmetrical" blob and starts becoming one of the extreme shapes.

They found a specific threshold (a number they calculated as roughly 0.037).

Below this number: The city is happy being a symmetrical, balanced blob. It is the most random it can be.
Above this number: The symmetrical blob is no longer the best option. It becomes "unstable." The city wants to break symmetry and split into the Clique or Anti-Clique shape, but it hasn't fully committed to one yet until it crosses the final line.

The Big Picture: Why This Matters

The authors also prove some foundational math that connects this to the real world of large networks (like social networks or the internet).

They show that if you have a massive network with specific rules, and there is only one best blueprint (one optimal graphon), then almost every single network that follows those rules will look exactly like that blueprint. The "weird" networks that don't look like the blueprint are so rare they are practically non-existent.

However, if there are two best blueprints (like at the tipping point), then the network could look like either one, and the choice is a matter of chance.

Summary Analogy

Think of the "Edge-2star Model" as a game of Musical Chairs played by a billion people.

The rules (edge and 2star density) are the music.
The optimal graphon is the arrangement of chairs that allows the most people to dance randomly without breaking the rules.
The paper shows that for most music tempos, there is only one perfect chair arrangement.
But at a specific tempo, the music forces the dancers to suddenly split into two distinct groups: either everyone huddles in one corner (Clique) or everyone spreads out to the edges (Anti-Clique).
Right at the moment the music changes, the dancers are frozen in indecision, equally likely to choose either formation.

This paper maps out exactly where that music changes and proves that for most of the song, the dancers have only one way to move, but at the climax, they have two equally valid, but very different, ways to dance.

Technical Summary: Optimal Graphons in the Edge-2Star Model

Problem Statement
This paper investigates the structure of large, dense random graphs subject to "hard" constraints on the density of edges ( $e$ ) and the density of 2-stars ( $t$ ). A 2-star (or "cherry") is a subgraph consisting of three vertices and two edges. The authors analyze the space of graphons (limits of large graphs) that maximize the Shannon entropy $S(g)$ subject to fixed values of $e$ and $t$ . The primary goal is to characterize the "typical" structure of these graphs by identifying the unique or non-unique entropy-optimal graphons across different regions of the parameter space $(e, t)$ .

The study focuses on two specific regimes:

High 2-star density: The region where $t$ is close to its theoretical maximum for a given $e$ .
Low 2-star density: The region near the Erdős-Rényi curve ( $t = e^2$ , or reduced density $\tilde{t} = t - e^2 = 0$ ).

Methodology
The authors employ the graphon formalism, treating graphs as limits in the space $\mathcal{W}$ . The entropy of a graphon $g$ is defined as $S(g) = \int_0^1 \int_0^1 H(g(x,y)) dx dy$ , where $H(u) = -\frac{1}{2}(u \ln u + (1-u)\ln(1-u))$ .

The methodology relies on:

Variational Analysis: Using Lagrange multipliers ( $\alpha, \beta$ ) to derive self-consistency equations for the degree function $d(x) = \int g(x,y) dy$ . Stationary points of the entropy functional satisfy $g(x,y) = (1 + \exp(-(\alpha + \beta(d(x)+d(y)))))^{-1}$ .
Multipodal Reduction: Proving that stationary points must be "multipodal" (taking finitely many values), reducing the infinite-dimensional optimization problem to a finite-dimensional one.
Asymptotic Expansions:
- Near the maximum density boundary, the authors use asymptotic analysis of the Lagrange multipliers (which diverge) to show that optimal graphons are "clique-like" or "anti-clique-like."
- Near the Erdős-Rényi curve ( $\tilde{t} \approx 0$ ), they utilize power-series expansions of the entropy function $H(u)$ around $u=1/2$ . By analyzing the moments of $(g(x,y) - 1/2)$ , they demonstrate that optimal graphons are bipodal and vary analytically with parameters.
Stability Analysis: Investigating the Hessian of the entropy functional restricted to the space of bipodal graphons to determine local maximality and identify bifurcation points where symmetry is broken.

Key Contributions and Results

Phase Transition at $e=1/2$ (High Density Regime):
The authors prove the existence of an open set in the $(e, \tilde{t})$ plane near the maximum possible 2-star density. Within this set:
- For $e > 1/2$ , the unique entropy optimizer is clique-like (bipodal, with one large cluster of high degree).
- For $e < 1/2$ , the unique entropy optimizer is anti-clique-like (bipodal, with one large cluster of low degree).
- On the line segment $e = 1/2$ , there are two distinct optimal graphons (one clique-like, one anti-clique-like).
  This establishes a discontinuous phase transition across $e=1/2$ , where the typical graph structure changes abruptly.
Analyticity and Uniqueness Near Erdős-Rényi:
For small values of $\zeta = \sqrt{(e-1/2)^2 + \tilde{t}}$ , the authors prove that the entropy-maximizing graphon is unique and bipodal. The parameters of this graphon ( $a, b, c, d$ ) are analytic functions of $(e, \tilde{t})$ everywhere except at the singular point $(1/2, 0)$ . This result bridges the gap between the regions $e < 1/2$ and $e > 1/2$ , showing a single "phase" just above the Erdős-Rényi curve.
Bifurcation and Symmetry Breaking:
Along the line $e=1/2$ , the authors determine the critical value $\tilde{t}^* \approx 0.03727637$ where the symmetric bipodal graphon (with $b=1-a$ and $c=d=1/2$ ) ceases to be a local maximizer of the entropy.
- For $\tilde{t} < \tilde{t}^*$ , the symmetric graphon is a local maximizer.
- For $\tilde{t}^* < \tilde{t} \le 0.0625$ , symmetric bipodal graphons exist but are not local maximizers.
- For $\tilde{t} > 0.0625$ , no symmetric bipodal graphons exist.
  This identifies the precise point where the system transitions from a unique symmetric phase to a regime where symmetry is broken (leading to the clique/anti-clique duality described in the high-density regime).
Foundational Theorems:
The paper provides rigorous proofs for two general theorems relating constrained random graphs to graphon optimization:
- Theorem 5: The Boltzmann entropy (the growth rate of the number of graphs with specific subgraph densities) equals the maximum Shannon entropy of a graphon satisfying those density constraints.
- Theorem 6: If the entropy-optimizing graphon is unique, then all but an exponentially small fraction of large graphs with the specified densities are structurally close (in cut metric) to that optimal graphon.

Significance and Claims
The paper claims to provide the first rigorous derivation of non-constant, unique optimal graphons for a model with competing hard constraints (edges and 2-stars) in specific parameter regimes. It demonstrates that "hard" constraints allow for the characterization of typical large graphs that are not Erdős-Rényi.

The authors emphasize that their results clarify the nature of phase transitions in random graph ensembles. Specifically, they show that:

Phase transitions in these models correspond to sharp structural changes in the "typical" large graph.
The edge-2star model exhibits a discontinuous transition (non-uniqueness of the optimizer) at $e=1/2$ for high densities, contrasting with the continuous behavior near the Erdős-Rényi curve.
The work extends previous findings on the edge-triangle model to the edge-2star model, addressing the "upper tail" behavior (high density of 2-stars) which is distinct from the "lower tail" behavior studied in other contexts.

The paper does not propose new applications or experimental setups but aims to solidify the theoretical foundation connecting large deviation principles, graphon theory, and the statistical mechanics of constrained random graphs.