Sampling Colorings with Fixed Color Class Sizes

Many interesting problems in combinatorics and its applications can be formulated as problems about independent sets, matchings, graph cuts, or colorings with global constraints. Thus, the ability to sample those fundamental objects with constraints solves a broad range of nuanced questions and strengthens current techniques and tools used for sampling. We begin by providing examples of some fundamental objects that we can sample and how introducing constraints alters the sampling problem.

One example comes from the ferromagnetic Ising model, a statistical physics model of graph cuts and magnets. It is possible to approximately count [20] and sample the states of the model [35] for all parameters and all graphs. However, when restricting the magnetization (number of vertices on one side of the cut/ number of particles with a positive spin), an algorithmic thresholds emerges. For the ferromagnetic Ising model with fixed magnetization, Carlson, Davies, Kolla, and Perkins established a computational threshold [4], meaning that there are regimes of temperature and magnetization for which efficient sampling algorithms exist and regimes in which no sampling is possible unless NP=RP (example of dynamical threshold also shown in [23]). Another example of interest comes from independent sets, often studied using the hard-core model. When introducing a size constraint on the independent sets, Davies and Perkins [9] showed the existence of a computational threshold; there exists ${\alpha }_c$ such that it is possible to sample independent sets of size $\alpha n$ for in polynomial time, but no sampling algorithm exists for $\alpha >{\alpha }_c$ unless NP=RP. Work of Jain, Michelen, Pham, and Vuong [17], establishes fast mixing of the down-up walk on independent sets of size $k\le (1-\delta ){\alpha }_c$.

Placing constraints on the size of the object is natural for statistical physics models, since they differentiate between settings where the number of particles can vary, called grand canonical ensembles, versus settings where the number of particles is fixed, called canonical ensembles. In practice, there are a lot more results in sampling algorithms for the grand canonical ensemble, since placing an additional constraint adds a layer of complexity. Under additional constraints the behavior of the system can change completely; for example, a well behaved system (like the ferromagnetic Ising model on a random graph) can exhibit “glassy” behavior with the imposition of a constraint on the magnetization [28].

Observe that the examples of constraints we have mentioned so far are one-dimensional. In this paper we will explore the instance of placing multiple global constraints on the model. More precisely, we will show that given an integer vector (with some assumptions on it), we can sample colorings in which color class sizes form the requested vector. It is a delicate problem since each of the color class sizes is an independent set of restricted size, and moreover, the union of colors should cover all the vertices of the graph. We introduce the background about sampling colorings as well as known existence results in the next subsection.

Before looking at colorings with constraints, we give background for sampling colorings with no constraints, since this problem is also far from being well understood. The following is a classical conjecture about sampling colorings [19, 38]:

Moreover, it is conjectured that a simple Markov chain, the Glauber dynamics, achieves this.

There has been a lot of progress in the past 30 years towards the resolution of the conjecture. In his seminal paper, Jerrum proved it for $q\ge 2\mathrm{\Delta }+1$ [19]. An exciting result by Vigoda improved that to sampling colorings with $q>\frac{11}{6}\mathrm{\Delta }$ [38]. There were also a lot of substantial improvements on the bounds for special families of graphs [10, 30, 13, 27, 11, 31, 14, 37, 7]. For general graphs, $q$ was further improved to $(11/6-\epsilon )\mathrm{\Delta }$ by Chen, Delcourt, Moitra, Perarnau, and Postle [6], and recently to $q\ge 1.809\mathrm{\Delta }$ by Carlson and Vigoda [5].

Despite the impressive progress in this direction, the problem presents a considerable challenge and might require many more ideas to decrease the necessary amount of colors down to $\mathrm{\Delta }+2$. Thus, it seems important to ask the following questions: How refined are our current tools and techniques? How well can we control the colorings that we can sample?

We now define the size constraints on color classes we have previously mentioned.

Let us describe perhaps the simplest case of $\overrightarrow{n}$-colorings, equitable colorings.

Note that if $q$ divides $n$, then all color class sizes must be equal.

Erdős conjectured in 1964 that any graph of maximum degree $\mathrm{\Delta }$ has an equitable $(\mathrm{\Delta }+1)$-coloring. In 1970, Hajnal and Szemerédi gave a proof of the conjecture [12]. Later, Kierstead and Kostochka provided a simpler proof, which also gives a polynomial-time algorithm for finding such a coloring. [22].

As a corollary of our main theorem, we establish a polynomial-time algorithm for approximately sampling uniform equitable colorings when $q\ge 2\mathrm{\Delta }$.

In a more general version of the theorem, we show the existence of a sampling algorithm for colorings that we call “skewed”, establishing their existence as a corollary.

As a simple corollary we obtain the existence of such colorings.

To the best of our knowledge, very little is known about the existence of skewed colorings beyond the equitable case (this can also be thought of as a way to generalize Hajnal and Szemerédi’s theorem). One can apply a result by Hurley, Joos, and Lang [16] to guarantee that the complement of the graph can be decomposed into cliques of constant size, which is equivalent to finding a proper coloring with constant color class sizes, but the coloring requires linearly many colors.

We conjecture that the following bound on color class sizes (matching the size of an independent set guaranteed to exist in a graph of maximum degree $\mathrm{\Delta }$) suffices.

Note that the conditions on $n_i$ are tight for a union of $(\mathrm{\Delta }+1)$-cliques, and the floor can not be improved to a ceiling, since a union of $(\mathrm{\Delta }+1)$-cliques together with one isolated vertex would serve as a counterexample.

Note as well that no assumption on $q$ is made, though the assumptions on $n_i$ and ${\Vert \overrightarrow{n}\Vert }_1$ already imply that $q\ge \mathrm{\Delta }+1$. Since $q\ge 2\mathrm{\Delta }$ constitutes a natural barrier for many approaches related to sampling colorings, a first step in proving Conjecture 8 might be to prove existence under the stronger condition that all $n_i\le \lfloor {\displaystyle \frac{n}{2\mathrm{\Delta }}}\rfloor$.

We also conjecture that it should be possible to sample colorings in that regime, although the proof would require new ideas.

Let us give definitions of some statistical physics models that we use throughout the paper.

The following model is called anti-ferromagnetic Potts model, it is a generalization of another popular statistical physics model called anti-ferromagnetic Ising model. It differentiates between improper and proper colorings by introducing weights that penalize improper colorings.

Note that at $w=0$ the partition function counts the number of proper colorings, and the Gibbs measure is simply a uniform distribution over proper colorings. If the number of colors satisfies $q\ge \mathrm{\Delta }+1$, a proper coloring exists, and thus the partition function at $w=0$ is non-zero. Even though the probability distribution requires $w$ to be non-negative and real, it is possible to work with the partition function for complex $w$. Liu, Sinclair, and Srivastava proved that in the complex plane around $w=0$ there exists a zero-free region for $Z_G(w)$ [25].

Using their zero-freeness result and a theorem by Barvinok [1], they get a deterministic algorithm for approximately counting proper colorings of a graph $G$ with bounded maximum degree and a sampling algorithm for colorings of $G$. We will explain more on how zero-freeness results can be useful for combinatorial algorithms in the next section.

We will use a variant of the Potts model with external fields (weights) for each of the colors. Since the model is only defined over proper colorings, we will, for simplicity, refer to it as the coloring model (equivalently it can be defined over all colorings with monochormatic edges having penalty $w=0$).

We will often drop the subscripts of ${\mathbb{P}}_{G,\overrightarrow{\lambda }}$ where there is no confusion.

As in the previous model, the probability distribution requires $\overrightarrow{\lambda }$ to be a non-negative real vector. However, we can still analyze the partition function for complex $\overrightarrow{\lambda }$, which is explained in the subsection below.

An extremely powerful property of the model in a certain parameter regime is the absence of complex zeros (zero-freeness) of the partition function. It can imply properties of the model, like deterministic counting [40], Spectral Independence [8], Central Limit Theorems [29], Strong Spatial Mixing [36], and thus has applications in approximation and sampling algorithms.

There is a lot of existing work that establishes zero-freeness for different models and with different motivations. For example, Lee–Yang theorem shows that, for the ferromagnetic Ising model, the zeros of the partition function lie on the complex unit circle for any graph [39]. One of the theorem’s implications is the absence of phase transition for non-zero external field. See also more work on the hard-core model [33], the Ising model [34], [32], and the monomer-dimer model [15]. It is important to note that in most cases one has to assume that a graph has bounded maximum degree $\mathrm{\Delta }$, since the zero-freeness radius often depends on $\mathrm{\Delta }$.

Our motivation for proving zero-freeness is getting very precise control over the cumulants (expectation, covariances and more) of the color class sizes. Derivatives of $\log Z$ are tightly connected with these cumulants, and thus showing zero-freeness of $Z$ lets us control the cumulants via convergent power series.

For example, zero-freeness implies linear upper bounds on the cumulants of any order. As one of the consequences, we can compute the asymptotics of the determinant of the covariance matrix, which will be important for the runtime of our algorithm. Moreover, zero-freeness allows us to Taylor expand the characteristic function of the random vector of color class sizes and establish a Local Central Limit Theorem (LCLT). We use this for the rejection sampling part of our algorithm, see an overview in Subsection 1.5 and details in Section 3 of the extended version.

Let us now give an overview of the zero-freeness result for the coloring model (see Definition 12). The approach we are taking is similar to the blueprint developed by Liu, Sinclair, and Srivastava for the Potts model with penalty [25] (see Definition 10), however, we need to generalize their result to a multivariate partition function and handle $q$ parameters (one for each color) instead of one. This is done so that each color receives its own variable, which lets us regulate each color class size. Generalizing existing tools to work in multivariate settings gives control over different parameters, which allows for better understanding and efficient algorithms for models with global constraints.

The following corollary of this result lets us rephrase it in terms of a zero-freeness ball with constant $l_{\mathrm{\infty }}$-radius:

The proof can be found in Section 2. The main idea behind the proof is an inductive argument in terms of the number of unpinned (i.e. not yet colored) vertices. For each iteration of the induction, we show that the ratio of the probability of a vertex to be colored $i$ vs be colored $j$ is very close to 1.

We note that in the paper of Liu, Sinclair, and Srivastava [25] the theorem holds generally for colorings they call “admissible” and requires fewer colors for triangle-free graphs. It is also mentioned that their result should generalize to list colorings. We expect these generalizations to hold for our model as well. Note that we write theorems in a general enough way that an improvement to the zero-freeness region would lead to an immediate improvement on the sampling and existence result. Bencs, Berrekkal, and Regts [2] recently relaxed the condition on the number of colors for the Potts model (with penalty parameter for monochromatic edges) from $q\ge 2\mathrm{\Delta }$ to $q\ge (2-\eta )\mathrm{\Delta }$, where $\eta \ge 0.002$. By adapting their ideas, we suspect a similar improvement is possible for our main results.

As one of our main theorems, we prove a Local Central Limit Theorem (LCLT), which states that the distribution of color class sizes in the coloring model approaches a multivariate Gaussian distribution pointwise. We also obtain asymptotic control over the eigenvalues and determinant of the covariance matrix, and thus can lowerbound the probability of sampling an $\overrightarrow{n}$-coloring. This is the main ingredient that is needed for the rejection sampling procedure.

Note that if we choose $\overrightarrow{\lambda }=\overrightarrow{1}$ (corresponding to uniform distribution), by symmetry $𝔼[X_i]=n/q$. We show that if , $\exp \left(-\frac{1}{2}{(\overrightarrow{n}-\overrightarrow{\mu })}^{\top }{\mathrm{\Sigma }}^{-1}(\overrightarrow{n}-\overrightarrow{\mu })\right)=\mathrm{\Omega }(1)$, and so

This is an important component of the proof, since it provides a guarantee for the number of times a rejection sampling step has to be repeated to reach the desired coloring. We explain how that is done in the next subsection.

The proof of the LCLT uses two ingredients. The first one is the Taylor expansion of the logarithm of the characteristic function ($\phi :=𝔼[e^{i⟨t,X⟩}]$) , which can be done in the region where the characteristic function is non-zero (this region is contained in the original zero-freeness region of $Z(\overrightarrow{\lambda })$). We show that for small $t$, $\phi$ is dominated by the terms corresponding to expectation and covariances (see Subsection 3.3 in the extended version). For larger $t$ we utilize a lemma which shows an upper bound on the absolute value of the characteristic function, thus showing that the contribution of larger $t$ is negligible (see Subsection 3.4 in the extended version).

In this subsection we will explain how to sample equitable colorings and then in the next subsection we explain how to adjust the algorithm slightly to sample skewed colorings. We use the LCLT as the main ingredient to give us guarantees on the success of rejection sampling. This is a standard tool in sampling (see [21] for example).

By a classical result of Vigoda [38], there exists an algorithm that approximately samples colorings (uniformly) in $O(n\log n\log (1/\epsilon ))$ for $q\ge \frac{11}{6}\mathrm{\Delta }$. One can use the Glauber dynamics as the chain in that algorithm (see [3], [26] for relevant details on its mixing time). We use this as the first step in the rejection sampling algorithm.

Since the LCLT together with bounds on the determinant of the covariance matrix imply that $\pi (\overrightarrow{X}=\overrightarrow{x})=\mathrm{\Theta }\left(n^{-(q-1)/2}\right)$, it is easy to show that after $O(n^{(q-1)/2}\log (1/\epsilon ))$ iterations of rejection sampling, the probability of the failure of the algorithm is at most $1-\epsilon$. Hence, the total running time of the algorithm is $O\left(n^{(q+1)/2}\log (n)\log {(\frac{1}{\epsilon })}^2\right)$. Note that this algorithm actually lets us sample more than just equitable colorings. For any constant $c>0$ and $\overrightarrow{n}$ such that ${\sum }_i{n}_i=n$ and we know that the LCLT and bounds on eigenvalues of the covariance matrix imply that $\pi (\overrightarrow{X}=\overrightarrow{x})=\mathrm{\Theta }\left(n^{-(q-1)/2}\right)$, and hence the same rejection algorithm works.

One could also ask for deterministic algorithms to approximate the number of equitable colorings, just as the zero-freeness result of [25] gives a deterministic algorithm (FPTAS) for the total number of colorings. This should be possible using an algorithmic implementation of the LCLT, as in [18]. We leave this for future work.

It is natural to predict that one could sample skewed colorings ( for small $c$) the same way that we sample equitable colorings. However, there are several challenges that appear. One of such challenges is showing that we can find (algorithmically) weights $\overrightarrow{\lambda }$ such that they give the right (or close to the right) color class sizes in expectation. For the equitable colorings (and colorings with $O(\sqrt{n})$ deviation from equitable) it was enough to take $\overrightarrow{\lambda }=\overrightarrow{1}$ (to sample from the uniform distribution). To be able to sample colorings with a linear deviation from equitable, we need to find $\overrightarrow{\lambda }$ such that ${\Vert {𝔼}_{\overrightarrow{\lambda }}[\overrightarrow{X}]-\overrightarrow{n}\Vert }_{\mathrm{\infty }}\le c\sqrt{n}$. This will allow us to sample colorings from the Gibbs distribution corresponding to $\overrightarrow{\lambda }$ and use LCLT to show that rejection sampling works. Note that the probability distribution we care about only makes sense in the zero-freeness region, thus it is not enough to only find appropriate choice of weights, but also show that they reside within the zero-freeness region.

To find $\overrightarrow{\lambda }$, we discretize our zero-freeness region such that ${\lambda }_i=1+k_i\frac{1}{\sqrt{n}}$ for $i\in [q-1],k_i\in \{-\lfloor R\sqrt{n}\rfloor ,\mathrm{\dots },\lfloor R\sqrt{n}\rfloor \}$ (we keep ${\lambda }_q=1$ for simplicity). We show that the expectation map is $O(n)$-Lipschitz (Subsection 4.1 of the extended version) and since the distance between optimal $\overrightarrow{\lambda }$ and one of the candidate ${\overrightarrow{\lambda }}^{\prime }$ is at most $\frac{1}{\sqrt{n}}$ (in $l_2$-norm), the difference between expectations is at most $\sqrt{n}$ for each color. Hence, we simply run the rejection sampling for each of the candidate $\overrightarrow{\lambda }$ until we obtain an $\overrightarrow{n}$-coloring. Since there are $\mathrm{\Theta }(n^{(q-1)/2})$ candidates, the runtime is $O\left(n^q\log (n)\log {(\frac{1}{\epsilon })}^2\right)$.

To understand what colorings we can sample with this technique, we show that the expectation map (restricted to a certain hyperplane) is surjective on the zero-freeness region (Subsection 4.2 of the extended version), which let’s us show that this procedure works for any coloring such that $\sum n_i=n$ and ${\Vert \overrightarrow{n}-\frac{n}{q}\overrightarrow{1}\Vert }_{\mathrm{\infty }}\le cn$ for $c$ small enough.

We also need to make sure that we can sample from the Gibbs distribution corresponding to $\overrightarrow{\lambda }$. This can be done by running the Glauber dynamics for $O(n\log n)$ steps. We prove the mixing time for $q\ge 2\mathrm{\Delta }+1$ using a standard path coupling technique in Subsection 4.3 of the extended version.

Figure 1 shows a diagram of the structure of the proof. Note that for sampling equitable colorings only the middle layer of the figure is necessary.

This extended abstract only contains some of the proofs; for full proofs, see the full version [24].

Recall the partition function and Gibbs measure of the coloring model:

For it to have a probabilistic interpretation, we would need ${\lambda }_i\in {ℝ}^{+}$, but we can still consider the partition function as a multivariate polynomial over the complex numbers.

The aim of this section is to show that in ${ℂ}^q$ there exists a ball $B$ around $\overrightarrow{1}$ such that $\forall \overrightarrow{\lambda }\in B$, $Z_G(\overrightarrow{\lambda })\ne 0$.

The proof here uses the framework of Liu, Sinclair and Srivastava [25] for the Potts model, in which the weight of a configuration is determined by the number of monochromatic edges in the coloring.

A variable $\omega$ specifies the “penalty” for a monochromatic edge. Let $m_G(\sigma )$ be the number of monochromatic edges introduced by the coloring $\sigma$. The partition function of the Potts model is a sum over all colorings (including improper ones), where the weight of a coloring is proportional to ${\omega }^{m_G(\sigma )}$. In other words, the partition function for the Potts model is

Note that this partition function is univariate. In contrast, our partition function is multivariate, since each color has its own weight; part of our work is therefore to lift several key ingredients of their proof to the multivariate case. Note also that in our model there are no monochromatic edges, so the penalty for such edges is simply $\omega =0$.

Since all the steps had to be adapted for our model, we will provide detailed calculations, and we utilize the structure and definitions of [25] for the acquainted reader to track differences easily.

Throughout this section we fix the constants $\nu :=0.9$, ${\epsilon }_R:={10}^{-2}{\mathrm{\Delta }}^{-2}$, and ${\epsilon }_I:={10}^{-4}{\mathrm{\Delta }}^{-4}$. We will use $\ln$ to denote the principal branch of the logarithm, which is analytic on $ℂ\setminus (-\mathrm{\infty },0]$ and satisfies $\arg (z):=\mathrm{Im}\ln z\in (-\pi ,\pi )$.

We will commonly refer to the following assumptions on $\overrightarrow{\lambda }\in {ℂ}^q$.

The main result we will prove is the following:

The assumptions from Definition 20 are expressed in terms of the logarithm of the ratio between components of $\overrightarrow{\lambda }$. That may not be practical for some applications, but it can be shown that any $\overrightarrow{\lambda }\in {ℂ}^q$ sufficiently close to $\overrightarrow{1}$ (for example, in ${\mathrm{\ell }}_{\mathrm{\infty }}$-distance) satisfies those.

Hence, we may derive the following corollary from Theorem 22:

The inductive proof not only shows that $Z_G(\overrightarrow{\lambda })\ne 0$, but actually gives a lower bound on its norm (which, despite being exponentially decreasing in $n$, will be of use later in bounding $\left|\log Z_G(\overrightarrow{\lambda })\right|$).

We will prove Theorem 22 with a slightly stronger assumption; some vertices of the graph may already be “pinned” to a color. That will allow us to proceed by induction on the number of unpinned vertices of the graph. We will formalize this idea through the following definition:

We will also introduce the following operation, which from a partially-$q$-colored graph $(G,\tau )$ generates another partially-$q$-colored graph $(\tilde{G},\tilde{\tau })$ which has one unpinned vertex fewer:

Since we are working with a model that only allows proper colorings, we will never want to pin a vertex to a color which is already present in its neighborhood. Thus, following the notation from [25], we will classify the colors as either good or bad (for a given vertex):

We will denote $(G,\tau )$ as $G$, despite the abuse of notation, whenever it is clear from context that we are referring to a partially-colored graph and there is no ambiguity with respect to the underlying partial coloring $\tau$. That extends as well to $Z_G$ (in place of $Z_{G,\tau }$) and ${𝒞}_G$ (in place of ${𝒞}_{G,\tau }$).

Next, we develop the definitions needed to frame the zero-freeness problem recursively, in terms of graphs which have fewer unpinned vertices.

We would like to relate $R_{G,v}^{(i,j)}(\overrightarrow{\lambda })$ to the partition function of a graph with fewer unpinned vertices than $G$. The numerator $Z_{G,v}^{(i)}(\overrightarrow{\lambda })$ can be related to the graph in which we pin vertex $v$ to color $i$, while the denominator $Z_{G,v}^{(j)}(\overrightarrow{\lambda })$ can be related to the graph in which we pin vertex $v$ to color $j$. Next, we define a sequence of graphs that allows us to interpolate between these two cases.

One can then derive a recurrence relation that expresses the ratios in $G$ in terms of the marginal pseudo-probabilities in each of the $G_k^{(i,j)}$.

In this subsection we introduce the ingredients from complex analysis we will need for the proof. The first three lemmas are from [25], while the last three are refinements of simple facts that were implicitly used in [25].

Let $D$ be a domain in $ℂ$ with the following properties:

• $\mathrm{■}$

  For any $z\in D$, $\mathrm{Re}(z)\in D$.

• $\mathrm{■}$

  For any $z_1,z_2\in D$, there exists a point $z_0\in D$ such that one of the numbers $z_1-z_0,z_2-z_0$ has zero real part while the other has zero imaginary part.

• $\mathrm{■}$

  If $z_1,z_2\in D$ are such that either $\mathrm{Im}(z_1)=\mathrm{Im}(z_2)$ or $\mathrm{Re}(z_1)=\mathrm{Re}(z_2)$, then the segment $[z_1,z_2]$ lies in $D$.

As remarked by Liu, Sinclair and Srivastava [25], a rectangular region symmetric about the real axis will satisfy all of the above properties.

The first point of the next lemma is needed to show that the function

satisfies the conditions of the previous lemma.

The next lemma gives us a way to lower-bound the sum of complex numbers, if we know that the angles between them are small enough.

An important part of the proof will require going from bounds on $z$ to bounds on $e^z$, and viceversa. That’s what the following two lemmas provide.

Finally, a result in the same vein as Lemma 42.

The main idea of the proof of the zero-freeness result of Theorem 22 is to pick a vertex $u$ and rewrite the partition function as a sum of $Z_{G,u}^{(i)}(\overrightarrow{\lambda })$ for all $i\in {\mathrm{\Gamma }}_u$. If we can prove that the angles between these terms are small, then it is enough for one of the terms to be non-zero for the whole sum to be non-zero (see Lemma 42).

Both the zero-freeness of $Z_{G,u}^{(i)}(\overrightarrow{\lambda })$ and the fact that the angles are small are shown by induction on the number of unpinned vertices of the graph. For the first, we simply use that $Z_{G,u}^{(i)}(\overrightarrow{\lambda })={\lambda }_i^{\mathrm{deg}(u)-1}{Z}_{\tilde{G}}(\overrightarrow{\lambda })$, where $\tilde{G}$ is the graph obtained by pinning vertex $u$ to color $i$. For the second, we need to bound the argument of the ratios $R_{G,u}^{(i,j)}$. For that purpose, we use Lemma 37, in which we derived a recursive formula that expresses $R_{G,u}^{(i,j)}$ in terms of marginal pseudo-probabilities of certain graphs $G_k^{(i,j)}$, which all have one fewer unpinned vertex than $G$.

The following lemma summarizes the statements constituting our induction hypothesis.