On the critical fugacity of the hard-core model on regular bipartite graphs

This paper establishes long-range order for the hard-core model on regular bipartite graphs and the integer lattice $\mathbb{Z}^d$ above a fugacity threshold of order $\frac{\log d}{d}$, thereby confirming that the critical fugacity for the latter scales as $d^{-1+o(1)}$ in high dimensions.

The Gist

The Big Picture: A Game of "No Touching"

Imagine a giant grid (like a chessboard, but in many dimensions). On this grid, you want to place "guests" (particles) on the squares. However, there is one strict rule: No two guests can sit next to each other. If you sit on a square, your immediate neighbors must stay empty.

This is the Hard-Core Model. It's a mathematical way to study how particles behave when they repel each other.

Now, imagine you have a "hunger" parameter called Fugacity ($\lambda$).

• Low Fugacity: You are picky. You don't want many guests. The grid stays mostly empty. Everyone is relaxed, and it doesn't matter who sits where; there's no pattern.
• High Fugacity: You are very hungry. You want to pack as many guests as possible onto the grid without breaking the "no touching" rule.

The Big Question: At what point does the grid suddenly snap into a specific, organized pattern? Does it become a crystal? Or does it stay a chaotic mess?

The Setting: The Two-Color Grid

The authors focus on a specific type of grid called a Bipartite Graph. Think of a checkerboard. It has two colors: Black and White.

• Every Black square is only connected to White squares.
• Every White square is only connected to Black squares.

The two largest groups of guests you can fit on this board are:

1. The Black Team: Fill every Black square, leave all White squares empty.
2. The White Team: Fill every White square, leave all Black squares empty.

The paper asks: If we get very hungry (high fugacity), will the guests naturally choose to be mostly on the Black squares OR mostly on the White squares?

This phenomenon is called Long-Range Order. It's like a crowd of people suddenly deciding, "Okay, everyone stand on the left side of the room!" or "Everyone stand on the right!" instead of mixing randomly.

The Discovery: How Hungry Do We Need to Be?

For a long time, mathematicians knew that if you get extremely hungry, the grid will organize. But they didn't know exactly how hungry you need to be for this to happen, especially in high dimensions (like a 100-dimensional grid).

Previous guesses were way off. Some thought you needed to be astronomically hungry. Others thought you needed to be moderately hungry.

The Authors' Breakthrough:
They proved that the "tipping point" (the critical fugacity) happens when the hunger level is roughly $\frac{\log d}{d}$, where $d$ is the number of dimensions.

• The Metaphor: Imagine a party in a room with $d$ exits. If the room is huge (high $d$), you don't need to be that hungry to get everyone to crowd into one corner. The math shows that the "crowding" happens much earlier (at a lower hunger level) than previously thought, but it still requires a specific amount of pressure.

The Tools: How They Solved It

To prove this, the authors used a clever mix of two strategies:

1. The "Sparse Exposure" (Peeking at the Puzzle)

Imagine trying to guess the pattern of a giant mosaic. Instead of looking at the whole thing at once, you look at a few scattered tiles.

• The authors developed a method called Sparse Exposure. They looked at small, random patches of the grid to see if a pattern was forming.
• They realized that if the grid has good "expansion" (meaning it's well-connected and doesn't have dead ends), looking at just a few tiles gives you a huge amount of information about the whole grid.
• Analogy: It's like trying to guess the weather in a whole country by checking the wind in just a few random towns. If the towns are well-connected, a few readings tell you everything.

2. The "Chessboard" Strategy (Reflection Positivity)

To prove this works for the infinite grid (the real world), they used a technique called the Chessboard Estimate.

• The Metaphor: Imagine you have a giant, infinite floor. You want to prove the tiles are arranged in a pattern. Instead of checking the whole floor, you cut the floor into small, identical square tiles (like a chessboard).
• You prove that if one small tile has a "defect" (a guest sitting in the wrong place), it costs a lot of "energy" (happiness).
• Because the floor is made of repeating tiles, if one tile is "wrong," it forces the neighbors to be "wrong" too, creating a chain reaction. The authors showed that at high hunger, these "defects" are so expensive that the grid must choose a side (Black or White) to avoid them.

The Results in Plain English

1. For Finite Graphs (Like a Torus): They proved that on a finite, multi-dimensional grid (like a donut shape in 100 dimensions), if the hunger is above a certain low threshold, the guests will almost certainly crowd into either the "Black" side or the "White" side. They won't mix.
2. For the Infinite Grid ($\mathbb{Z}^d$): This is the big prize. They proved that for the infinite grid (the standard mathematical model of space), there are two distinct states at high hunger.
   • State A: The grid is mostly "Black."
   • State B: The grid is mostly "White."
   • This confirms a long-standing belief that the "phase transition" (the switch from chaos to order) happens at a specific, calculable point.

Why Does This Matter?

• Physics: This helps us understand how crystals form. Why do atoms suddenly line up in a perfect grid when cooled down? This math explains the "tipping point" where disorder turns into order.
• Computer Science: These models are used to understand algorithms for counting and sampling. Knowing when a system becomes "rigid" (ordered) helps computer scientists design better algorithms.
• Math: It solves a puzzle that has been open for decades. It bridges the gap between what happens on small, finite grids and what happens in the infinite universe.

Summary Analogy

Imagine a dance floor with two colors of tiles.

• Low Music (Low Fugacity): People dance randomly. Some are on black, some on white. No one cares.
• High Music (High Fugacity): The beat gets intense. Suddenly, everyone realizes that to fit the most people on the floor without bumping into each other, they must all dance on the Black tiles (or all on the White tiles).
• The Paper's Contribution: The authors calculated the exact volume of the music (the "hunger") required to trigger this sudden, synchronized dance. They proved that in high-dimensional spaces, this synchronization happens much sooner than we thought, and they gave us the precise formula for it.

Technical Summary

1. Problem Statement

The paper investigates the hard-core model on finite and infinite graphs, specifically focusing on the emergence of long-range order (LRO) at high fugacities ($\lambda$).

• The Model: Given a graph $G=(V,E)$ and fugacity $\lambda > 0$, the model defines a probability measure on independent sets (configurations $\sigma \in \{0,1\}^V$ where no two adjacent vertices are occupied). The probability of a configuration is proportional to $\lambda^{|\sigma|}$.
• The Phenomenon: At low $\lambda$, configurations are sparse and correlations decay. At high $\lambda$, on bipartite graphs with partitions $(E, O)$, the system is expected to exhibit LRO, meaning typical configurations concentrate heavily on one partition class (either mostly $E$ or mostly $O$), breaking the symmetry.
• The Gap: While it is known that LRO fails for $\lambda \lesssim e/\Delta$ (where $\Delta$ is the degree), the precise threshold for the onset of LRO on high-dimensional lattices ($\mathbb{Z}^d$) and discrete tori ($\mathbb{Z}_L^d$) was unknown. Previous bounds suggested the critical fugacity $\lambda_c$ scales as $d^{-1/3}$ or $d^{-1/4}$, while heuristics suggested it should be of order $d^{-1}$.
• Goal: The authors aim to determine the asymptotic order of the critical fugacity $\lambda_c(d)$ as $d \to \infty$ for regular bipartite graphs, specifically proving that $\lambda_c(d) = \Theta(\frac{\log d}{d})$.

2. Methodology

The paper employs a multi-stage approach combining information-theoretic entropy methods, graph expansion properties, and reflection positivity.

A. Finite Graph Analysis (Part I)

The core of the work is a new quantitative bound for finite, $\delta$-regular, bipartite graphs satisfying specific expansion properties.

1. Free Energy Functional: The authors define a free energy functional $I(\sigma) = S(\sigma) + (\log \lambda)E|\sigma|$, where $S$ is Shannon entropy. They utilize a variational principle to bound the partition function.
2. Coarse Graining & Interface Energy: They introduce a "coarse-grained" variable $\phi$ representing the local density of occupied sites. They define an "interface energy" $\Phi$ (roughness) measuring the disagreement between the even and odd phases.
3. Sparse Exposure & Shearer's Inequality: To bound the entropy of the configuration, they use a technique called sparse exposure. They reveal information about the configuration on a sparse random subset of vertices.
   • Gain Terms: They show that if the interface energy $\Phi$ is high (indicating a mix of phases), the entropy is penalized significantly (surface tension).
   • Loss Terms: They bound the entropy of the revealed information using a generalized Shearer's inequality.
4. Expansion Properties: The proof relies on two expansion conditions:
   • Global Expansion: Measured by the Cheeger constant $h(G)$.
   • Local Expansion: A novel condition (Definition 1.5) involving the existence of a probability distribution over connected subgraphs (trees) that efficiently "cover" the graph. This allows for efficient encoding of the revealed information.

B. Discrete Tori (Part II)

The authors apply the finite graph results to discrete tori $\mathbb{Z}_L^d$.

• They prove that $\mathbb{Z}_L^d$ satisfies the required local expansion and global expansion properties.
• Specifically, they construct dominating trees using Hamming codes to satisfy the local expansion condition with optimal parameters.
• This establishes LRO for $\mathbb{Z}_L^d$ when $\lambda > C \frac{\log d}{d}$.

C. Infinite Lattice $\mathbb{Z}^d$ (Part III)

To transfer the result from finite tori to the infinite lattice $\mathbb{Z}^d$, they use a Chessboard Peierls Argument.

1. Reflection Positivity: They utilize the fact that the hard-core model on $\mathbb{Z}^d$ is reflection positive.
2. Chessboard Estimate: They define a "bad" event (a contour where the phase is mixed) on a mesoscopic block. Using the chessboard estimate, they bound the probability of these contours appearing in the infinite lattice by the probability of the same event on a finite torus of fixed size ($L=6$).
3. Symmetry Breaking: By showing that "bad" contours are exponentially rare at high fugacity, they prove the existence of multiple Gibbs measures (distinct even and odd phases).

3. Key Contributions and Results

Main Theorem (Theorem 1.1)

For the hard-core model on the $d$-dimensional integer lattice $\mathbb{Z}^d$ ($d \ge 2$), there exists a constant $C > 0$ such that for any fugacity:
$$\lambda > C \frac{\log d}{d}$$
the model admits multiple Gibbs measures. This implies the existence of long-range order (phase coexistence).

Critical Fugacity Order

This result significantly tightens the upper bound on the critical fugacity $\lambda_c^+(d)$.

• Previous Best: $\lambda_c^+(d) \le C \frac{\log^2 d}{d^{1/3}}$ (Samotij–Peled, 2014).
• New Result: $\lambda_c^+(d) \le C \frac{\log d}{d}$.
• Significance: This matches the lower bound (up to the logarithmic factor) derived from the general mixing condition on trees, suggesting the true critical fugacity is of order $\frac{\log d}{d}$ (or possibly $\frac{1}{d}$, as conjectured).

General Finite Graph Theorem (Theorem 1.7)

The paper provides a general criterion for LRO on any finite $\delta$-regular bipartite graph $G$:

• If $G$ has global expansion $h(G)$ and satisfies a local expansion property with parameters $C_{LE}, M_{LE}$, then LRO occurs when:
  $$\log(1+\lambda) > C \frac{C_{LE}}{\delta} \max \left( \log \frac{\delta |V|}{h(G) r}, \frac{\delta |V|}{h(G) r M_{LE}} \right)$$
• This theorem is sharp for graphs like the hypercube and tori, but the authors provide a counter-example (Example 14.4) showing that without specific expansion properties, the threshold can be as high as $\frac{\log \delta}{\delta}$.

Specific Bounds

• Partition Function: They derive precise bounds on the specific free energy (Corollary 1.4), improving upon trivial bounds.
• Hypercube: They confirm LRO for the hypercube $\mathbb{Z}_2^d$ at $\lambda > C \frac{\log d}{d}$, determining the critical fugacity up to the log factor.

4. Significance

1. Resolution of a Long-Standing Open Problem: The paper resolves the order of magnitude of the critical fugacity for the hard-core model on high-dimensional lattices, a problem that has been open since the 2004 breakthrough by Galvin and Kahn.
2. Methodological Innovation: The combination of sparse exposure with generalized Shearer's inequality and local expansion provides a powerful new toolkit for analyzing phase transitions in statistical mechanics on graphs. This approach avoids some of the technical limitations of previous cluster expansion or entropy methods.
3. Bridging Finite and Infinite: The rigorous transfer of results from finite tori to the infinite lattice using reflection positivity and chessboard estimates demonstrates a robust framework for studying infinite-volume limits in high dimensions.
4. Conjecture: The authors conjecture that the true critical fugacity is actually $\lambda_c(d) \sim \frac{e}{2d}$ (removing the $\log d$ factor), suggesting that the $\log d$ term in their bound is an artifact of the method rather than the physics of the model.

In summary, Hadas and Peled establish that long-range order in the hard-core model on high-dimensional regular bipartite graphs emerges at fugacities of order $\frac{\log d}{d}$, bringing the theoretical understanding of this phase transition significantly closer to the conjectured optimal bound of $\frac{1}{d}$.