Rapid Mixing via Coupling Independence for Spin Systems with Unbounded Degree

Let $G=(V,E)$ be a graph with maximum degree $\mathrm{\Delta }$ and $[q]=\{1,2,\mathrm{\dots },q\}$ a set of colors. Given a set of color lists $L_v\subseteq [q],v\in V$, a proper list-coloring $X\in {[q]}^V$ assigns a color $X_v\in L_v$ to each vertex $v\in V$ such that adjacent vertices receive different colors. In a special case when $L_v=[q]$ for all $V\in V$, the list coloring becomes the standard graph $q$-coloring. We use $\mu$ to denote the uniform distribution over all proper list-colorings in $G$. For the list coloring, in each step, the Glauber dynamics picks a random vertex $v$ and update its color to a random available color. There is a long line of works studying the mixing and relaxation time of Glauber dynamics e.g. [33, 45, 9].

In the era of spectral independence, the proper list-coloring has been re-studied by a series of works [16, 24, 19]. Though the technique varies, all these works established some coupling independence results for the proper list-coloring. For list colorings on triangle-free graphs, let ${\alpha }^{\star }\approx 1.763$ denote the unique positive solution to the equation $\alpha =\exp (1/\alpha )$. When $|L_v|>({\alpha }^{\star }+\delta )\mathrm{\Delta }$, the $O_{\delta }(1)$-coupling independence can be established by techniques in [16, 24]. Our framework gives the optimal relaxation time of Glauber dynamics even if the maximum degree of $G$ is unbounded.

Under the condition of Theorem 1, the relaxation time of the Glauber dynamics has been studied by many previous works. Combining the spectral independence technique [1, 3] with the correlation decay analysis [27, 26], two independent works [16, 24] proved the polynomial relaxation time $n^{O(1/\delta )}$ of Glauber dynamics. For graphs with bounded maximum degree $\mathrm{\Delta }=O(1)$, Chen, Liu and Vigoda [21] established the $O_{\mathrm{\Delta },\delta }(n)$ relaxation time, where $O_{\mathrm{\Delta },\delta }(\cdot )$ hides a constant factor like ${\mathrm{\Delta }}^{O({\mathrm{\Delta }}^2/\delta )}$. For general graphs with possibly unbounded maximum degree, Jain, Pham and Vuong [29] proved the first almost linear relaxation time $O_{\delta }(n{e}^{{(\log \log n)}^2})=O_{\delta }(n^{1+o(1)})$. Their proof combined the techniques in [21] with the coupling analysis in [28]. Compared to previous results, Theorem 1 gives the optimal linear relaxation time for general graphs.

We prove Theorem 1 by first verifying the coupling independence condition (Definition 7) and then applying our comparison result (Theorem 9). Theorem 1 requires $|L_v|\ge ({\alpha }^{\star }+\delta )\mathrm{\Delta }$ because the current best coupling independence result requires this number of colors but our comparison result does not require such a strong condition. It is conjectured that $O_{\delta }(1)$-coupling independence should hold for proper list-coloring in general graphs when $|L_v|\ge (1+\delta )\mathrm{\Delta }+O(1)$.

Our comparison framework can prove optimal relaxation time for Glauber dynamics on proper list-colorings of graphs (with potentially unbounded degree) as long as Conjecture 2 holds.

The standard relation between relaxation time and mixing time implies that the Glauber dynamics mixes in time $O_{\delta }(n^2\log q)$, which yields a sampling algorithm for the uniform distribution $\mu$ of graph colorings in time $O_{\delta }(\mathrm{\Delta }{n}^2\log q)$ because each step of Glauber dynamics can be simulated in time $O(\mathrm{\Delta })$. However, in terms of sampling algorithm, our technique would directly give an algorithm (not the Glauber dynamics) in time ${\tilde{O}}_{\delta }(\mathrm{\Delta }n)$. Since the input graph $G$ contains $\mathrm{\Delta }n$ edges, the running time is near-linear in the input size.

The next example is the hardcore model. Let $G=(V,E)$ be a graph. Let $\lambda >0$ be the fugacity. The hardcore model defines a distribution $\mu$ over all independent sets $S\subseteq V$ in $G$ such that $\mu (S)\propto {\lambda }^{|S|}$. Let $\mathrm{\Delta }\ge 3$ denote the maximum degree of graph $G$. There is a critical threshold (a.k.a. uniqueness threshold) for the tree uniqueness phase transition [36]

such that if $\lambda \le {\lambda }_c(\mathrm{\Delta })$ the correlation between two vertices decays in their distance; if $\lambda >{\lambda }_c(\mathrm{\Delta })$, the long-range correlation exists. A computational phase transition occurs at the same threshold. If , polynomial time sampling algorithm exists [46]; if $\lambda >{\lambda }_c(\mathrm{\Delta })$, the sampling problem is hard unless NP = RP [44, 25]. The mixing and relaxation time of the Glauber dynamics for hardcore model were also extensively studied [41, 28, 23]. Recent works analyzed Glauber dynamics via spectral independence [3]. The optimal $O_{\delta }(n\log n)$ mixing time and the optimal $O_{\delta }(n)$ relaxation time were established when $\lambda \le (1-\delta ){\lambda }_c(\mathrm{\Delta })$ for general graphs [21, 15, 12].

However, for the hardcore model on bipartite graphs, the picture is not very clear. Consider the hardcore model in a bipartite graph $G=(V=V_L\uplus V_R,E)$. Let ${\mathrm{\Delta }}_L$ denote the maximum degree in the left part. Assume $3\le {\mathrm{\Delta }}_L$. It is recently known that the uniqueness threshold for the hardcore model on the bipartite graph can be refined to ${\lambda }_c({\mathrm{\Delta }}_L)\ge {\lambda }_c(\mathrm{\Delta })$ where $\mathrm{\Delta }\ge {\mathrm{\Delta }}_L$ is the maximum degree of the bipartite graph [39, 13]. The Glauber dynamics is also proved to have polynomial mixing time when [13].

On the other side, when $\lambda >{\lambda }_c({\mathrm{\Delta }}_L)$, the lower bound in [44] does not hold for bipartite graphs and the problem is #BIS-hard [7], where #BIS is the problem of counting the independent sets in bipartite graphs. A line of works (e.g. [31, 8, 38, 17, 32]) studied various sampling algorithms in the low-temperature (large $\lambda$) regime.

Within the critical threshold , we consider “balanced” bipartite graphs. Let ${\mathrm{\Delta }}_R$ be the maximum degree in $V_R$. We say a bipartite graph is $\theta$-balanced if ${\mathrm{\Delta }}_R\le \theta {\mathrm{\Delta }}_L$.

For the mixing time, again, the standard relation gives $O_{\delta ,\theta }(n^2)$ mixing time of the Glauber dynamics. However, since the bipartite graph hardcore is a monotone system, our technique also implies the ${\tilde{O}}_{\delta ,\theta }(n)$ mixing time of Glauber dynamics starting from the independent set containing all vertices in the left part: $X_0=V_L$. Formally, for any $S\in \mathrm{\Omega }(\mu )$,

The previous work [13] established the ${(\frac{{\mathrm{\Delta }}_L\log n}{\lambda })}^{O(1/\delta )}{n}^2$ relaxation time for the Glauber dynamics, which, by the standard relation, implies the ${(\frac{{\mathrm{\Delta }}_L\log n}{\lambda })}^{O(1/\delta )}{n}^3\log \frac{1+\lambda }{\lambda }$ mixing time. The previous result holds for general bipartite graphs as long as $\lambda \le (1-\delta ){\lambda }_c({\mathrm{\Delta }}_L)$. For balanced bipartite graphs, we obtained the optimal relaxation time $O_{\delta ,\theta }(n)$ and the near-optimal mixing time ${\tilde{O}}_{\delta ,\theta }(n)$, which significantly improved the dependency to $n$ and ${\mathrm{\Delta }}_L$ compared to the previous result. For example, in the near critical case when $\lambda =(1-\delta ){\lambda }_c({\mathrm{\Delta }}_L)=\mathrm{\Theta }(1/{\mathrm{\Delta }}_L)$, previous result gives ${\mathrm{\Delta }}_L^{O(1/\delta )}{n}^2\cdot \mathrm{polylog}(n)$ relaxation time and ${\mathrm{\Delta }}_L^{O(1/\delta )}{n}^3\cdot \mathrm{polylog}(n)$ mixing time but our result gives $O(n)$ relaxation time and $n\cdot \mathrm{polylog}(n)$ mixing time. However, our result works only on balanced bipartite graphs. The result in [13] is still state-of-the-art for general bipartite graphs.

Finally, we point out that our technique could also recover many previous $O(n)$ relaxation time results for anti-ferromagnetic 2-spin systems in [11]. See Remark 10 for one example.

In this section, we give our general results for spin systems. Let $G=(V,E)$ be a graph. Let $[q]=\{1,2,\mathrm{\dots },q\}$ be a set of $q\ge 2$ spins. For each vertex $v\in V$, let vector $b_v\in {ℝ}_{\ge 0}^q$ be the external field at vertex $v$. For each edge $e\in E$, let symmetric matrix $A_e\in {ℝ}_{\ge 0}^{q\times q}$ be the interaction matrix at edge $e$. A spin system defines a Gibbs distribution $\mu$ over ${[q]}^V$ such that,

We use $\mathrm{\Omega }(\mu )\subseteq {[q]}^V$ to denote the support of the Gibbs distribution $\mu$.

Let $\mathrm{\Lambda }\subseteq V$ be a subset of vertices. Given any pinning $\tau \in {[q]}^{V\setminus \mathrm{\Lambda }}$, we define a conditional distribution ${\mu }^{\tau }$ by for any configuration $\sigma \in {[q]}^V$,

In words, ${\mu }^{\tau }$ is a Gibbs distribution obtained for $\mu$ by removing all edges $e\subseteq V\setminus \mathrm{\Lambda }$ and putting a constraint that every vertex in $v\in V\setminus \mathrm{\Lambda }$ must take the value ${\tau }_v$. In particular, if $\tau$ is feasible (e.g. $\tau$ belongs to the support of the marginal distribution ${\mu }_{V\setminus \mathrm{\Lambda }}$), then ${\mu }^{\tau }$ is exactly the conditional distribution induced by $\mu$ given the condition $\tau$. For all spin systems considered in this paper, it holds that ${\sum }_{\sigma }{w}^{\tau }(\sigma )>0$ for all $\tau$. The distribution in (2) is well-defined. Furthermore, for any subset $S$, we use ${\mu }_S^{\tau }$ to denote the marginal distribution on $S$ projected from ${\mu }^{\tau }$.

The following condition plays a key role in the proof of our main results. Let $\rho :V\to {\mathbb{N}}_{>0}$ be a function that maps every vertex $v\in V$ to a positive integer. We call the function $\rho$ the Hamming weight function. For any two (possibly partial) configurations $\sigma ,\tau \in {[q]}^{\mathrm{\Lambda }}$, where $\mathrm{\Lambda }\subseteq V$, define their weighted Hamming distance with respect to $\rho$ by

The notion of coupling independence was introduced explicitly in [14] to study the spectral independence property. For example, for Boolean distributions¹¹1The influence matrix and spectral independence are also defined for general distributions with $q\ge 2$. See [16] for the detailed definition. ($q=2$), given any pinning $\tau \in {\{-,+\}}^{V\setminus \mathrm{\Lambda }}$, the $|\mathrm{\Lambda }|\times |\mathrm{\Lambda }|$ influence matrix [3] is defined by

where $u,v\in \mathrm{\Lambda }$ and $\tau \wedge v^{\pm }$ denotes the pinning $\tau$ together with $v$ taking the value $\pm$. A distribution $\mu$ is $C$-spectrally independent if the maximum eigenvalue of ${\mathrm{\Psi }}_{\mu }^{\tau }$ is at most $C$ for any pinning $\tau$. It is not hard to show that $C$-coupling independence implies $C$-spectral independence. Hence, recent works [14, 19, 18] utilized coupling independence to establish the spectral independence for various spin systems.

In this work, we find more applications for coupling independence beyond establishing spectral independence. We build some comparison results of Markov chains via coupling independence. As a by-product result, we also show that the coupling independence gives fast sampling algorithms.

Let $\mu$ be a Gibbs distribution over ${[q]}^V$ on graph $G=(V,E)$. For any $\mathrm{\Lambda }\subseteq V$, we use $G[\mathrm{\Lambda }]$ to denote the induced subgraph of $G$ on vertex set $\mathrm{\Lambda }$.

In the above definition, ${\mu }^{\tau }$ is a distribution on ${[q]}^V$. In every step, the Glauber dynamics picks $v\in V$ uniformly at random then resamples the value on $v$. If $v\notin \mathrm{\Lambda }$, the value of $v$ after resampling is always ${\tau }_v$. Indeed, ${\mu }^{\tau }$ is essentially the same as ${\mu }_{\mathrm{\Lambda }}^{\tau }$. But, considering ${\mu }^{\tau }$ would help us simplify some results and proofs. The following is our main comparison result.

The theorem is proved in the full version ([10, Section 4]). See Section 3 for a proof overview.

The above theorem is a comparison result between two kinds of relaxation times. Consider the case when parameters of $\mu$ are close to the critical threshold so that the relaxation time $T_{\text{rel}}^{\text{GD}}(\mu )$ is hard to analyze. By choosing a sufficiently small $\eta$, suppose for any $\mathrm{\Lambda }\in D(\eta )$ and any $\tau \in {[q]}^{V\setminus \mathrm{\Lambda }}$, the conditional distribution ${\mu }^{\tau }$ falls into an easy regime. The relaxation time $T_{\text{rel}}^{(\eta )}(\mu )$ is easy to analyze. Theorem 9 boosts the relaxation time from an easy regime to the hard regime if $\mu$ satisfies the coupling independence and the maximum degree $\mathrm{\Delta }$ is greater than a constant ${\mathrm{\Delta }}_0$.

When applying Theorem 9 to a specific spin system with Gibbs distribution $\mu$, we first need to show that the $\mu$ satisfies the coupling independence property. Next, we choose a small constant $\eta$ to guarantee that $T_{\text{rel}}^{(\eta )}(\mu )$ is easy to analyze. Now, the constant parameter ${\mathrm{\Delta }}_0$ in Theorem 9 is fixed. If the maximum degree $\mathrm{\Delta }\le {\mathrm{\Delta }}_0=O(1)$ is bounded, then since the coupling independence implies the spectral independence, the previous work [21] already established the optimal relaxation time for $\mu$. If the maximum degree $\mathrm{\Delta }\ge {\mathrm{\Delta }}_0$, we can apply our boosting result to bound the relaxation time. We show how to prove Theorem 1 and Proposition 3 via Theorem 9.

The next question is how to establish the coupling independence condition for spin systems. Previously, spectral independence was known for many spin systems. The coupling independence was often a by-product result when proving spectral independence. Hence, it is known for some specific spin systems such as subgraph world [14], $b$-matching [18] and coloring in high girth graphs [19].

In this paper, we give a tool to turn many existing spectral independence results into coupling independence results. A large family of spin systems is $2$-spin systems. Let $G=(V,E)$ be a graph with maximum degree $\mathrm{\Delta }\ge 3$. Let $0\le \beta \le \gamma$ be the edge interactions such that $\gamma >0$. Let $\lambda >0$ be the external field. Let $\mu$ be the Gibbs distribution on $G$ with parameters $\beta ,\gamma ,\lambda$ such that for any $\sigma \in \{-,+\}$, $\mu (\sigma )\propto {\lambda }^{n_{+}(\sigma )}{\beta }^{m_{+}(\sigma )}{\gamma }^{m_{-}(\sigma )}$, where $n_{+}(\sigma )$ is the number of vertices $v$ with ${\sigma }_v=+$ and $m_{\pm }(\sigma )$ is the number of edges $\{u,v\}$ with ${\sigma }_u={\sigma }_v=\pm$. The 2-spin system is said to be ferromagnetic if $\beta \gamma >1$ and anti-ferromagnetic if .

Anari, Liu, and Oveis Gharan [3] analyzed the spectral independence for the hardcore model. Chen, Liu, and Vigoda [20] extended the analysis to general 2-spin systems. Recall that the influence matrix ${\mathrm{\Psi }}_{\mu }^{\tau }$ is defined in (4). The maximum eigenvalue ${\mathrm{Eig}}_{\max }({\mathrm{\Psi }}_{\mu }^{\tau })$ can be upper bounded by the total influence from one vertex

The RHS is called the total influence bound. For 2-spin systems, the analysis is performed on the Self-Avoiding-Walk (SAW) tree [46]. Roughly speaking, fix a vertex $v$, the SAW tree $T_v$ enumerates all the SAWs in graph $G$ starting from $v$. By defining a proper 2-spin system on $T_v$, one can use the total influence from the root in $T_v$ to upper bound the total influence from $v$ in $G$, and thus establish the spectral independence for Gibbs distribution $\mu$. In [20], a weighted version of (8) is studied to deal with general 2-spin systems. We give the following result for coupling independence.

As a consequence, all the spectral independence results for 2-spin systems in [20] can be turned into coupling independence results in black-box. For the hardcore model in bipartite graphs (Theorem 5 and Theorem 6), we can also use the above result to transform the total influence bound in [13] into coupling independence result.

Theorem 16 is proved by constructing a recursive coupling in the full version ([10, Section 7]). Fix a vertex $v$ in $G$. We build a coupling $(X,Y)$ between ${\mu }^{v^{+}}$ and ${\mu }^{v^{-}}$ and show the discrepancy between $X$ and $Y$ are bounded by the total influence in the SAW tree $T_v$. Suppose $v$ has $d$ neighbors $u_1,u_2,\mathrm{\dots },u_d$. We split $v$ into $d$ copies $v_1,v_2,\mathrm{\dots },v_d$ such that $v_i$ only has one neighbor $u_i$. Define the pinning ${\sigma }_i$ such that $v_j$ for $j\ge i$ takes the value $+$ and $v_j$ for takes the value $-$. Then ${\mu }^{v^{+}}={\mu }^{{\sigma }_0}$ and ${\mu }^{v^{-}}={\mu }^{{\sigma }_d}$. We couple each adjacent ${\mu }^{{\sigma }_{i-1}}$ and ${\mu }^{{\sigma }_i}$, then merge them into a coupling between two endpoints ${\mu }^{{\sigma }_0}$ and ${\mu }^{{\sigma }_d}$. For each adjacent pair, the only difference between ${\sigma }_i$ and ${\sigma }_{i-1}$ is the pinning at $v_i$. Hence, we first couple the only neighbor $u_i$ of $v_i$ then construct the coupling recursively if the coupling at $u_i$ fails. This recursive processing essentially enumerates all SAWs from $v$. We can relate the coupling with the SAW tree to prove the theorem.

For multi-spin systems such as list-coloring, we can mimic the recursive coupling for 2-spin systems. Since the previous spectral independence results for list-coloring were also obtained via the SAW tree [24, 16], a similar proof gives the coupling independence.