🔢 mathematics

An edge-bicolored graph approach to the Ising model on random regular graphs

This paper presents an exact solution for the ferromagnetic Ising model on random regular graphs by expressing the partition function as a generating function of labeled edge-bicolored graphs, thereby deriving the free energy and confirming a second-order phase transition with mean-field critical exponents through analytic combinatorics.

Original authors: Michael Borinsky, Shiyue Ren, Maximilian Wiesmann

Published 2026-07-10

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Michael Borinsky, Shiyue Ren, Maximilian Wiesmann

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a giant, chaotic party where thousands of guests (let's call them "spins") are standing in a circle. Each guest is holding a sign that says either "Up" or "Down." The rule of the party is simple: everyone wants to agree with their neighbors. If two neighbors hold the same sign, they feel happy (low energy); if they disagree, they feel grumpy (high energy). This is the Ising model, a famous way physicists try to understand how magnets work.

Usually, figuring out exactly how this party behaves is a nightmare. If the guests are arranged in a perfect grid (like a chessboard), we can solve it. If they are arranged in a simple, infinite tree, we can solve that too. But what if the guests are connected in a completely random way, like a tangled web of friendships where everyone has exactly the same number of friends? This is a random regular graph.

In this paper, Michael Borinsky, Shiyue Ren, and Maximilian Wiesmann throw a wild new party for this problem. Instead of using the usual heavy math tools (like probability theory), they bring in analytic combinatorics—a branch of math that treats counting problems like a game of building with LEGO bricks.

The Magic Trick: Coloring the Edges

Here is the secret sauce the authors discovered. To count all the possible ways the guests can arrange their signs, they didn't look at the signs directly. Instead, they imagined the connections (the handshakes) between the guests. They decided to paint every handshake either Red or Blue.

They found a magical rule: if you count all the possible ways to paint these handshakes with these specific rules, you get the exact answer for the party's "happiness" (which physicists call the partition function). It's like solving a puzzle by counting the colors of the pieces rather than the pieces themselves.

By using this "edge-bicolored" counting trick, they were able to write down a perfect, closed-form formula for the free energy. Think of free energy as the "temperature" of the party's overall mood. They calculated exactly what this mood is when the number of guests becomes infinite.

The Big Reveal: A Phase Transition

The most exciting part of their discovery is what happens when you change the temperature.

Imagine you start with a very hot party. Everyone is jittery, flipping their signs randomly. No one agrees with anyone. This is the "disordered" phase. As you slowly cool the room down, something magical happens at a very specific temperature. Suddenly, the guests start to lock into a pattern. They all agree to hold "Up" or all hold "Down" (or a mix that favors one side). This is the "ordered" phase, where the magnetism kicks in.

The authors proved that this switch happens at a precise critical temperature, $T_c = 2J / (k_B \log(k / (k-2)))$ .

$J$ is how much the guests care about agreeing with each other.
$k$ is the number of friends each guest has.
$k_B$ is just a constant that helps with the units.

If the room is hotter than $T_c$ , the party is chaotic. If it's colder, the party organizes itself. The paper proves this transition is a second-order phase transition. In plain English, this means the change is smooth but dramatic: the "magnetization" (the average direction of the signs) grows slowly from zero as the room cools, rather than jumping suddenly.

What They Ruled Out

The authors are very clear about what doesn't happen.

No magic for random fields: If you add a strong external magnetic field (forcing everyone to pick "Up" no matter what), the party never has a sudden phase transition. The guests just follow the orders smoothly. The "jump" only happens when the room is empty of outside orders (zero magnetic field).
No weird exponents: Some models of magnets behave strangely, with "critical exponents" (numbers that describe how fast things change) that are messy and unique to the shape of the graph. The authors found that for these random graphs, the exponents are exactly the same as the "mean-field" model. This confirms that random graphs act like they are in "infinite dimensions" because, locally, they look like trees (no loops). The math proves the behavior is standard and predictable, not weird.

How Sure Are They?

The authors didn't just guess or run computer simulations. They proved it.

They derived an exact formula for the free energy (Theorem 1.1).
They used rigorous math to show that this formula has a specific point where it stops being smooth (the phase transition).
They calculated the exact numbers for how the magnetism grows and how the "sensitivity" of the system changes near that point.

They found that the "critical exponents" (the numbers describing the sharpness of the transition) are:

$\alpha = 0$ (Specific heat)
$\beta_{mag} = 1/2$ (How magnetism grows)
$\gamma = 1$ (Magnetic susceptibility)
$\delta = 3$ (How magnetism responds to a field at the critical point)

These numbers match the "mean-field" theory perfectly. The paper confirms that even though the graph is random, the physics behaves exactly like the simplest, most idealized version of a magnet.

The Bottom Line

This paper is a victory for "counting" as a way to solve physics problems. By turning the messy problem of random magnets into a neat problem of counting colored connections, the authors found the exact answer for how these systems behave. They showed that when you have a random network of friends, the whole group will spontaneously agree on a direction once the temperature drops below a specific, calculable point, and they did it with the precision of a mathematical proof, not just a simulation.

Technical Summary: An Edge-Bicolored Graph Approach to the Ising Model on Random Regular Graphs

Problem Statement
The paper addresses the challenge of obtaining an exact solution for the ferromagnetic Ising model on an ensemble of random regular graphs. While exact solutions exist for specific lattice structures (e.g., Onsager's solution for the 2D square lattice) and mean-field models, exact closed-form expressions for the free energy in the thermodynamic limit on random regular graphs have historically relied on probabilistic methods or matrix integrals restricted to planar graphs. The authors aim to solve this model for general random regular graphs (without planarity assumptions) using techniques from analytic combinatorics, specifically focusing on the annealed free energy where the partition function is averaged over the graph ensemble.

Methodology
The authors employ a combinatorial approach rooted in analytic combinatorics, diverging from the probabilistic methods used in prior rigorous works (e.g., [DM10; DMS13]). The core methodology involves three main steps:

Graphical Expansion: The partition function $Z_G(\beta, h)$ for a fixed graph $G$ is expanded using the high-temperature expansion (van der Waerden expansion). This rewrites the partition function as a sum over subgraphs $\gamma \subseteq E_G$ , weighted by vertex factors that depend on the parity of the degree of vertices in the subgraph.
Edge-Bicolored Graph Enumeration: The average partition function over the ensemble of $k$ -regular graphs, $Z_{n,k}$ , is reinterpreted as the generating function for labeled edge-bicolored graphs with specific vertex incidence constraints. This transformation allows the problem to be mapped onto the asymptotic enumeration of these combinatorial structures.
Asymptotic Analysis via Saddle-Point Method: Utilizing recent results on the asymptotic enumeration of edge-bicolored graphs (specifically [BMW25; BMW26]), the authors apply a saddle-point analysis to the resulting generating functions. The free energy in the thermodynamic limit is derived from the asymptotic behavior of these counts, reducing the problem to finding the global maximum of a specific potential function $V_k(\theta)$ defined on the unit circle.

Key Contributions and Results

Exact Free Energy Formula: The primary result (Theorem 1.1) provides an exact, closed-form expression for the free energy $f(\beta, h)$ of the Ising model on random $k$ -regular graphs in the thermodynamic limit. The formula is expressed in terms of the location $\theta^*$ of the global maximum of a potential function $V_k(\theta)$ , which depends on the inverse temperature $\beta$ , external field $h$ , and coupling $J$ .
Phase Transition Characterization: The analysis of the potential $V_k(\theta)$ $V_{k} (θ)$ reveals the nature of phase transitions:
- For non-zero external field ( $h \neq 0$ ), the model exhibits no phase transitions.
- At zero field ( $h=0$ ), the model undergoes a second-order phase transition at the critical inverse temperature $\beta_c = \frac{1}{2J} \log\left(\frac{k}{k-2}\right)$ . This critical point coincides with that of the Bethe lattice (Ising model on the infinite regular Cayley tree).
- For $\beta > \beta_c$ and $h=0$ , the system exhibits spontaneous magnetization due to the breaking of $\mathbb{Z}/2\mathbb{Z}$ spin-flip symmetry.
Critical Exponents: The paper derives the critical exponents for the phase transition at $(\beta_c, 0)$ $(β_{c}, 0)$ by analyzing the Taylor expansions of the free energy and magnetization near the critical point. The calculated exponents are:
- Specific heat exponent: $\alpha = 0$
- Magnetization exponent: $\beta_{\text{mag}} = 1/2$
- Susceptibility exponent: $\gamma = 1$
- Critical isotherm exponent: $\delta = 3$
  These values confirm that the model belongs to the mean-field universality class, consistent with the local tree-like structure of random regular graphs.
Combinatorial Interpretation of Magnetization: The authors provide a purely combinatorial interpretation of the magnetization as an enumeration of edge-bicolored graphs with a marked vertex, demonstrating that the thermodynamic limit of this enumeration matches the derivative of the free energy.

Significance and Claims
The paper claims to provide the first exact solution for the Ising model on random regular graphs using analytic combinatorics, offering a distinct alternative to probabilistic and matrix integral approaches. By expressing the free energy as the generating function of labeled edge-bicolored graphs, the authors establish a direct link between statistical mechanics on random graphs and asymptotic enumeration.

The significance of the work lies in its rigorous confirmation that the phase transition behavior of random regular graphs matches that of the Bethe lattice, validating the "locally tree-like" intuition. Furthermore, the derivation of mean-field critical exponents from a combinatorial framework reinforces the classification of this model within the infinite-dimensional mean-field universality class. The authors note that their approach allows for a detailed analysis of the free energy's analyticity, precisely identifying the locus of non-analyticity (phase transitions) through the behavior of the saddle points of the potential function.

The Magic Trick: Coloring the Edges

The Big Reveal: A Phase Transition

What They Ruled Out

How Sure Are They?

The Bottom Line

More like this