Zero-Freeness of the Hard-Core Model with Bounded Connective Constant

This paper establishes that the partition function of the hard-core model is zero-free in a complex neighborhood up to the connective constant threshold $\lambda_c(\mu)$, thereby proving the uniqueness and analyticity of the free energy density for infinite lattices beyond the traditional maximum degree bounds.

The Gist

Imagine you are trying to predict the weather in a massive, infinite city. You can't measure every single house, so you look at smaller neighborhoods (finite graphs) to guess what the whole city (infinite lattice) is doing.

In the world of physics and math, there's a famous puzzle called the Hard-Core Model. Think of it as a game of "musical chairs" played by invisible particles on a grid.

• The Rules: Particles want to sit on the chairs (vertices of a graph), but they are "hard-core." This means if one particle sits in a chair, no other particle can sit in the chairs immediately next to it. They need personal space.
• The Goal: Physicists want to know the "Free Energy" of this system. This is a fancy way of asking: "Is the system stable, or is it about to undergo a chaotic phase transition (like water turning to ice)?"

The Old Problem: The "Worst-Case" Guess

For decades, mathematicians tried to figure out when this system stays stable. They used a rule based on the Maximum Degree ($\Delta$).

• The Analogy: Imagine you are judging a party. To be safe, you assume the most popular person at the party has 100 friends. You then assume everyone has 100 friends.
• The Flaw: In a city grid (like a square lattice), most people only have 4 neighbors. But because the "worst-case" rule assumes everyone has the maximum possible connections, it forces the math to be very conservative. It says, "The system is only safe if the particles are very sparse." It misses the nuance that the city is actually quite orderly.

The New Discovery: The "Average" Reality

This paper introduces a smarter way to measure the complexity of the graph, called the Connective Constant ($\sigma$).

• The Analogy: Instead of assuming everyone has 100 friends, we count how many unique paths a person can take to walk around the city without ever stepping on their own footprints (Self-Avoiding Walks).
• The Insight: On a square grid, even though a person could theoretically have many connections, the number of unique, non-repeating paths they can take grows much slower than the "worst-case" scenario. The Connective Constant captures this "average" complexity rather than the "worst-case" chaos.

The Big Breakthrough: Finding the "Zero-Free" Zone

The core of the paper is about finding Zero-Free Regions.

• The Metaphor: Imagine the "Free Energy" is a landscape of hills and valleys. A "Zero" is a deep, bottomless pit where the math breaks down (a phase transition).
• The Goal: We want to prove that if we stay within a certain range of particle density (activity $\lambda$), we are walking on solid ground, far away from any pits.
• The Old Result: Previous math said, "You are safe only if you stay in this small, narrow valley near the edge."
• The New Result: The authors proved that by using the Connective Constant, we can walk much further! They found a wider, safer valley. They showed that the system remains stable (analytic) for much higher particle densities than previously thought possible, specifically up to a threshold determined by the Connective Constant ($\lambda_c(\sigma)$) rather than the Maximum Degree ($\lambda_c(\Delta)$).

How They Did It: The "Block Contraction" Trick

To prove this, the authors used a clever technique called Block Contraction.

• The Analogy: Imagine you are trying to prove that a long line of dominoes will fall in a predictable pattern.
  • Old Way: You check if one domino falling knocks over the next one. If the connection is weak, you can't be sure about the whole line.
  • New Way: The authors looked at blocks of $k$ dominoes at a time. They showed that even if you look at a whole chunk of the system, the "influence" of one part on another shrinks (contracts) very quickly.
  • The Magic: They proved that this "shrinking" effect works not just for real numbers (simple physics), but also for complex numbers (the tricky, abstract math used to find those "pits"). By proving the blocks contract in this complex world, they guaranteed there are no pits (zeros) in the safe zone.

Why This Matters

1. Better Predictions: For real-world materials (like crystals or magnetic grids), this tells us exactly how dense the particles can get before the material changes state.
2. Better Algorithms: In computer science, knowing where the "pits" are helps us build faster algorithms to simulate these systems. If we know the system is stable, we can calculate answers quickly.
3. Bridging the Gap: This paper connects two different ways of thinking about physics (correlation decay and zero-freeness), showing that they are two sides of the same coin.

In a nutshell: The authors stopped looking at the "worst-case" scenario for how crowded a system can get. Instead, they looked at the "realistic" structure of the grid. By doing so, they proved the system is much more robust and stable than we thought, opening up a larger safe zone for both physics predictions and computer algorithms.

Technical Summary

1. Problem Statement

The paper addresses the zero-freeness of the partition function for the hard-core model on finite graphs and its implications for the analyticity of the free energy on infinite lattices.

• Context: The hard-core model describes a gas of particles with hard-sphere interactions, mathematically equivalent to counting independent sets in a graph with activity $\lambda$. The partition function $Z_G(\lambda) = \sum_{I \in \mathcal{I}(G)} \lambda^{|I|}$ is central to the model.
• The Gap: Historically, zero-freeness results (regions in the complex plane where $Z_G(\lambda) \neq 0$) have been bounded by the maximum degree $\Delta$ of the graph. Specifically, zero-freeness was established up to the tree uniqueness threshold $\lambda_c(\Delta-1)$.
• The Motivation: For highly structured graphs (e.g., regular lattices like $\mathbb{Z}^2$), the maximum degree is a loose bound. The connective constant $\sigma$ (the exponential growth rate of self-avoiding walks) provides a more precise measure of structural complexity. While recent approximation algorithms (via correlation decay and Markov Chain Monte Carlo) have successfully utilized $\sigma$ to improve thresholds to $\lambda_c(\sigma)$, analogous zero-freeness results for complex zeros had been lacking.
• The Challenge: Existing definitions of the connective constant for finite graphs (e.g., log-depth or local definitions) were insufficient to guarantee uniform zero-freeness, as counter-examples showed they could not exclude zeros near critical points.

2. Methodology

The authors employ a multi-faceted approach combining combinatorial graph theory, statistical physics, and complex analysis.

A. New Definition of Connective Constant for Finite Graphs

The authors introduce a rigorous definition of the $k$-depth connective constant tailored for finite graphs to overcome the limitations of previous definitions.

• Definition: For a graph $G$ and vertex $v$, let $N_{\le k}(G, v)$ be the number of self-avoiding walks (SAWs) of length $\le k$ starting at $v$.
  • $\mu_k(G) = \sup_{v \in V} (N_{\le k}(G, v))^{1/k}$.
  • The lower connective constant for a family $\mathcal{H}$ is $\mu_{\inf}(\mathcal{H}) = \inf_{k \ge 1} \sup_{G \in \mathcal{H}} \mu_k(G)$.
• Justification: This definition ensures that for infinite lattices, the lower connective constant of their finite subgraphs equals the lattice's standard connective constant ($\mu_{\inf}(\mathcal{H}_L) = \sigma(L)$).

B. Block Contraction Technique

The core proof utilizes a block contraction framework, extending previous work on correlation decay to the complex domain.

• SAW Trees: The authors use Weitz's Self-Avoiding Walk (SAW) tree to reduce the computation of marginal probabilities on a graph $G$ to a tree structure.
• $k$-Layer Block Operators: Instead of analyzing the contraction of a single-step recurrence function (1-layer), they bundle $k$ steps into a $k$-layer block operator $F_{\lambda, T, k}$. This operator maps the "interface" at depth $k$ of the SAW tree to the root.
• Contraction Analysis:
  1. Real Contraction: They prove that for $\lambda < \lambda_c(d)$, the block operator contracts distances in a specific norm (using the potential function $\phi(x) = \text{arcsinh}(\sqrt{x})$) on the real interval $[0, \lambda]$.
  2. Complex Extension: Using a real-to-complex extension theorem (based on Shao-Sun [SS21]), they lift this contraction property from the real interval to a strip-like complex neighborhood $L_\delta([0, \lambda])$.

C. Inductive Proof of Zero-Freeness

They prove that if the block operator contracts within a complex region $Q$ (where $-1 \notin Q$), then the partition function is non-zero.

• By induction on the number of vertices, they show that the occupation ratio $R_{G,v} = Z_{\text{occ}}/Z_{\text{unocc}}$ remains within the safe region $Q$.
• Since $Z_G(\lambda) = Z_{\text{unocc}}(1 + R_{G,v})$, and $-1 \notin Q$, it follows that $Z_G(\lambda) \neq 0$.

D. Lifting to Infinite Lattices

To establish the analyticity of the free energy density $f_L(\lambda)$ for infinite lattices:

• They define the free energy as the thermodynamic limit of normalized partition functions over a Følner-van Hove sequence.
• Using Vitali's Convergence Theorem, they show that if the partition functions of all finite subgraphs are uniformly zero-free in a complex domain, the limiting free energy is unique and analytic in that domain.
• They introduce Assumption A (existence of a free abelian group of translations acting cocompactly) to generalize the result beyond simple lattices to quasi-transitive graphs.

3. Key Contributions

1. Definition of Finite Connective Constant: Proposed a robust definition ($\mu_{\inf}$) based on lower bounds of SAW counts that successfully bridges finite graph properties to infinite lattice behavior.
2. Zero-Freeness up to $\lambda_c(\sigma)$: Proved that for any family of graphs with lower connective constant $\mu$, the partition function is zero-free in a complex neighborhood of $[0, \lambda]$ for all $\lambda < \lambda_c(\mu)$. This matches the threshold achieved by correlation decay algorithms but applies to complex zeros.
3. Block Contraction Framework: Developed a novel proof technique using $k$-layer block operators to lift correlation decay properties from real intervals to complex strips, overcoming the limitations of 1-layer analysis.
4. Analyticity of Free Energy: Established the uniqueness and analyticity of the free energy density for infinite lattices up to the connective constant threshold, extending known results derived from maximum degree bounds.

4. Results

The paper provides specific quantitative improvements for various lattices. The new thresholds $\lambda_c(\sigma)$ are significantly higher than the traditional degree-based thresholds $\lambda_c(\Delta-1)$.

Lattice	Max Degree ($\Delta$)	Old Threshold $\lambda_c(\Delta-1)$	Connective Const. ($\sigma$)	New Threshold $\lambda_c(\sigma)$
Square ($\mathbb{Z}^2$)	4	1.688	2.638	2.145 (up to 2.538*)
Triangular	6	0.762	4.251	0.961
Honeycomb	3	4.000	1.848	4.976
Cubic ($\mathbb{Z}^3$)	6	0.762	4.739	0.822

*Note: The bound of 2.538 for the square lattice is achieved by incorporating specific refinements from Sinclair et al. [SSŠY17] regarding the Weitz tree structure.

5. Significance

• Theoretical Unification: The work unifies the understanding of phase transitions in statistical physics. It demonstrates that the connective constant is the fundamental parameter governing both algorithmic tractability (via correlation decay/MCMC) and the analyticity of thermodynamic quantities (via zero-freeness).
• Algorithmic Implications: Since zero-freeness in a complex region implies the existence of a Fully Polynomial-Time Approximation Scheme (FPTAS) for computing the partition function, this result suggests that efficient approximation algorithms exist for a wider range of activities on structured graphs than previously proven.
• Methodological Advancement: The introduction of block contraction for complex zero-freeness offers a powerful new tool for analyzing other statistical physics models where simple recurrence relations are insufficient.
• Resolution of Open Questions: It answers the open question of whether zero-freeness regions can be improved beyond maximum degree bounds for structured graphs, confirming that they can indeed be improved to the connective constant threshold.

In summary, this paper closes a critical gap between algorithmic results and statistical physics theory, proving that the structural complexity measured by the connective constant, rather than the local maximum degree, dictates the phase transition behavior and analytic properties of the hard-core model.