Sampling List Packings

The classic graph coloring problem is to determine, for a graph $G=(V,E)$ and number of colors $q$, whether there is a coloring $f:V\to [q]$ such that $f$ is proper in the sense that $f(u)\ne f(v)$ for every edge $uv\in E$. List coloring emerged in the late 20th century as an adversarial version of this problem [27, 13]. To define list coloring, we take a list size $q\in \mathbb{N}$ and assign to each $u\in V$ a list of allowed colors $L(u)$ of size $q$. One can think of the list assignment $L$ as supplied by an adversary who might try to prevent the existence of a coloring respecting the lists. If, under any choices of such an assignment of lists, the graph $G$ admits a proper coloring $f$ such that $f(u)\in L(u)$ for every vertex $u$, then we say that $G$ is $q$-list colorable (also known as $q$-choosable in some works). In some ways list coloring and classical graph coloring are similar, e.g., the complete graph on $n$ vertices requires $q\ge n$ for both problems. But all bipartite graphs can be colored with two colors, while $K_{n,n}$ requires lists of length $\mathrm{\Omega }(\log n)$ in the list coloring setting [13].

List coloring also arises naturally in various other ways. Notably, if we take a classic graph coloring problem and pre-color some vertices then we can express the problem of completing the coloring through list coloring. We set $L(u)$ to be the subset of the colors not used by any pre-colored vertex in the neighborhood of $u$ (though these lists may not have equal sizes). The idea of list coloring has been extended in several interesting directions, and in this work we study a very recent and structured variant known as list packing [6]. The setup is the same as for list coloring with a fixed list size $q$, but instead of seeking just one proper coloring where each vertex is colored from its list, we seek $q$ pairwise-disjoint proper colorings from the lists. We consider two colorings $f$ and $f^{\prime }$ of a graph disjoint if, for all vertices $u$ we have $f(u)\ne f^{\prime }(u)$. We call this collection of $q$ pairwise-disjoint proper list colorings a list packing. Given a graph $G$ and list size $q$, if a list packing can be found for any lists of size $q$ chosen by an adversary then we say that $G$ is $q$-list packable.

One motivation for list packing in [6] is to challenge the state-of-the-art in list coloring. For example, a folklore result states that a bipartite graph of maximum degree $\mathrm{\Delta }$ is $q$-list colorable for $q\ge (1+o(1))\mathrm{\Delta }/\log \mathrm{\Delta }$ (see also [1] and a recent improvement of the leading constant due to Bradshaw [4]). Amongst other foundational results on list packing, the folklore result was matched for the significantly more structured notion of list packing in [6]. A notable difference between known results for list packing and list coloring is that a general graph of maximum degree $\mathrm{\Delta }$ is $q$-list packable for $q\ge 2\mathrm{\Delta }$ (improved to $q\ge 2\mathrm{\Delta }-2$ for $\mathrm{\Delta }\ge 4$ in [8]); whilst such $G$ are $q$-list colorable for $q\ge \mathrm{\Delta }+1$ (and even $q=\mathrm{\Delta }$ if $\mathrm{\Delta }\ge 3$ and $G$ does not contain a clique on $\mathrm{\Delta }+1$ vertices [13]). Despite the gap in known results, there is scant evidence that more than $\mathrm{\Delta }+1$ colors are ever required for list packing [8, 6].

Early work on list packing has focused on the problem of existence, though many arguments for existence also provide efficient constructions of list packings. An extremal perspective on counting list packings was recently investigated by Kaul and Mudrock [21], and related problems where one seeks many list colorings or “flexible” list colorings are studied in [20, 7]. In this work we turn to the study of approximately counting the number of $L$-packings of a graph $G$ with a fixed $q$-list assignment $L$. This is a natural question by analogy with the same questions for graph coloring and list coloring: is there an efficient procedure that, given a graph $G$ and a number of colors $q$, approximates the number of proper $q$-colorings of $G$ (e.g., to within a factor 2)? This question is well-studied in the field of approximate counting and sampling, and is an important test-bed for algorithmic techniques. A longstanding open question is the existence of such an approximate counting algorithm that works for all $q\ge \mathrm{\Delta }+1$ on graphs of maximum degree $\mathrm{\Delta }$. An influential collection of results using various techniques requires conditions such as $q\ge e\mathrm{\Delta }+1$ [2], $q\ge 2\mathrm{\Delta }$ [17, 22], $q\ge 11\mathrm{\Delta }/6$ [26], and even $q\ge (11/6-ϵ)\mathrm{\Delta }$ for some small $ϵ>0$ [10, 9]. Another branch of research on the algorithmic aspects of counting graph colorings seeks to sample perfectly uniformly from the set of proper $q$-colorings of a graph. The pioneering result is due to Huber [15], with improvements and new techniques supplied in a number of later works [23, 22, 3, 16]. Interestingly, one application of such perfect samplers is to design approximate counting algorithms that can be faster than analogous approaches which use approximate samplers.

Motivated by simple and powerful ideas such as the Markov chain Monte Carlo approach to counting colorings due to Jerrum [17] (see also [25]), we seek similar results for list packing. The list packing problem, however, presents novel difficulties. Observe that finding a list coloring gets strictly easier as the list size $q$ grows. Supposing that one has a technique that works with lists of size $q_0$, then given larger lists one can take arbitrary subsets of the lists of size $q_0$ and apply the technique in a black-box fashion. In contrast, for list packing with larger $q$ we are required to find ever more list colorings which must also be pairwise-disjoint. Given lists of size $q>q_0$, it is not at all clear how to extend an arbitrary collection of $q_0$ pairwise-disjoint list colorings to a full list packing. The methods of [8, 6] provide evidence that showing the existence of a list packing does get easier with larger $q$, albeit for less straightforward and general reasons. Whether counting list packings should get easier as $q$ grows is another matter, but we confirm this principle in the setting of approximate counting by giving an algorithm that approximately counts list packings which works for all $q$ large enough in terms of the maximum degree.

Approximate counting of combinatorial objects such as list colorings, independent sets, and matchings corresponds to approximating the so-called partition function of a spin system from statistical physics. We are interested in the study of counting and sampling list packings as it presents an unusual type of spin system. Typically, the number of spins available for each vertex in a spin system is small. In the Ising model of magnetism vertices take a spin from $\{+,-\}$, and in the (antiferromagnetic) Potts model associated with proper $q$-colorings, the spins are the $q$ colors. Parameter ranges frequently studied for this model on graphs of maximum degree $\mathrm{\Delta }$ include the case when $q$ is close to $\mathrm{\Delta }+1$. The natural spin system associated with $q$-list packings, however, has $q!$ spins for each vertex. Since a vertex $u$ has a list of $q$ colors which we must decompose into $q$ choices, one for each list coloring in the packing, the spins for $u$ naturally correspond to permutations of the list $L(u)$. One of our contributions is to study a somewhat natural combinatorial problem which involves a spin system on bounded degree graphs with many more spins than commonly-studied examples. We hope that further insights into algorithmic techniques for approximate counting can be gained by studying an unusual spin system.

Our main result is the existence of an approximate counting algorithm for list packings. We define an $ϵ$-approximation of a real number $x$ as a real number $y$ satisfying $e^{-ϵ}\le x/y\le e^{ϵ}$. We use the standard notion of a fully polynomial-time randomized approximation scheme (FPRAS) for a counting problem. This is a randomized algorithm that, given $ϵ>0$, yields an $ϵ$-approximation of the true answer in time polynomial in the input size and $1/ϵ$.

Before we state the result, we need some more notation for list packings focusing on a specific list assignment $L$. Given a graph $G$ we call an assignment $L:V(G)\to 2^{\mathbb{N}}$ of lists of colors to the vertices of $G$ such that $|L(u)|=q$ for all vertices $u$ a $q$-list assignment of $G$. A proper coloring $f$ of $G$ such that $f(u)\in L(u)$ for all vertices $u$ is called an $L$-coloring, or a list coloring if the lists $L$ are understood from context. Given a graph $G$ and a $q$-list assignment $L$, we call a collection of $q$ pairwise-disjoint $L$-colorings of $G$ an $L$-packing. Note that an $L$-packing corresponds to permutation of the lists $L(v)$ for each vertex $v$.

We prove this result by analyzing the so-called “heat-bath Glauber dynamics” for list packing. Briefly, the state space is the set of list packings of the graph and transitions involve resampling a uniform random valid permutation of the list of a uniform random choice of vertex. We define “valid” carefully and analyze this Markov chain later, noting here that we prove Theorem 1 by establishing rapid mixing of this chain and hence an approximate sampling algorithm for a uniform $L$-packing under the same conditions.

A natural combinatorial problem on matchings in balanced bipartite graphs of large minimum degree emerges during the proof of Theorem 1, leading to a probabilistic result stated below that may be of independent interest. This is because the valid permutations of the list $L(v)$ correspond precisely to the perfect matchings in an auxiliary bipartite graph that we construct from the list packing on the neighbors of $v$. Throughout, we assume that $\mathrm{\Delta }$ and $q$ are fixed constants and do not analyze the case where they are allowed to depend on the number $n$ of vertices of $G$ as then algorithmic issues related to (perfectly) sampling perfect matchings in $2q$-vertex bipartite graphs become trivial³³3Given a bipartite graph of constant order which contains a perfect matching, sampling a perfect matching uniformly at random can be done in constant time, e.g. by exhaustively enumerating the perfect matchings and selecting one at random.. We do not attempt to optimize the dependence of the running time on $q$ or $\mathrm{\Delta }$.

Given a set $A$, we write ${𝒰}_A$ for the uniform distribution on $A$. When a fixed $q$ is clear from context, let $d_{\mathrm{C}}$ be the Cayley metric on the symmetric group $S_q$. That is, $d_{\mathrm{C}}(\rho ,{\rho }^{\prime })$ is the minimum number of transpositions which one must compose with $\rho$ to turn it into ${\rho }^{\prime }$. This is merely graph distance on the Cayley graph of $S_q$ generated by the transpositions. We associate perfect matchings in a balanced bipartite graph $H=([q]\bigsqcup [q],E)$ with permutations $\rho \in S_q$ where $(i,\rho (i))\in E$ for each $i$.

Given two random variables $X,Y$ defined on the discrete probability spaces $({\mathrm{\Omega }}_X,p_X)$ and $({\mathrm{\Omega }}_Y,p_Y)$, a coupling of $X,Y$ is a random variable $\gamma =(X^{\prime },Y^{\prime })$ defined on a probability space $({\mathrm{\Omega }}_X\times {\mathrm{\Omega }}_Y,p_{\gamma })$ such that $X$ and $X^{\prime }$ have identical distributions and $Y$ and $Y^{\prime }$ have identical distributions.

Given a Markov chain $Z_t$ with state space $\mathrm{\Omega }$ and transition matrix $P$, a coupling of $Z_t$ is a Markov chain $(X_t,Y_t)$ with state space $\mathrm{\Omega }\times \mathrm{\Omega }$ and transition matrix $\widehat{P}$ satisfying

That is, each coordinate of the coupling is a faithful copy of $Z_t$, though the transitions of the coordinates are not necessarily independent.

We prove Theorem 1 by the standard Markov chain Monte Carlo approach and the path coupling technique of Bubley and Dyer [5]. We study an ergodic Markov chain – the heat-bath Glauber dynamics – whose stationary distribution is uniform on the list packings of a graph, and use path coupling to show rapid mixing. Then a well-known and generic reduction from counting to sampling yields Theorem 1. Path coupling reduces the potentially challenging task of proving rapid mixing of a Markov chain to designing a coupling on adjacent states according to some graph $\mathrm{\Gamma }$ on the state space $\mathrm{\Omega }$. We largely follow the notation of [12] and consider

an ergodic Markov chain on state space $\mathrm{\Omega }$ with initial distribution $p_0$ and transition operator $P$. We denote the (unique) stationary distribution by $\pi$, and denote by $p_t:=P^t{p}_0$ the distribution of the state of the chain $ℳ$ after $t$ steps. We use the standard notion of mixing time of Markov chains given by

where $d_{\mathrm{TV}}$ is total variation distance.

Typically, we write $\omega$ and ${\omega }^{\prime }$ for states of the chain before a transition and $\sigma :=P\omega$, ${\sigma }^{\prime }:=P{\omega }^{\prime }$ for the (random) states after one step of the chain from $\omega$ and ${\omega }^{\prime }$ respectively.

The theorem may seem rather abstract, so we briefly discuss a well-known application to list coloring as a warm-up to the main argument for list packing. Let $G$ be a graph of maximum degree $\mathrm{\Delta }$ and let $L$ be a $q$-list assignment of $G$. Let $\mathrm{\Omega }$ be the set of $L$-colorings of $G$, and let $ℳ$ be the heat-bath Glauber dynamics on $\mathrm{\Omega }$, defined as follows. Note that states $\omega \in \mathrm{\Omega }$ are colorings and hence functions $V(G)\to \mathbb{N}$. A transition of $ℳ$ from a state $\omega$ is performed by choosing a vertex $u\in V(G)$ uniformly at random, sampling a color $c$ in $L(u)\setminus \omega (N(u))$, and moving to the state $\sigma$ with $\sigma (u)=c$ and $\sigma (v)=\omega (v)$ for all $v\ne u$. That is, the transition operator $P$ is defined via

1. 1.

   sampling a vertex $u\sim {𝒰}_{V(G)}$,

2. 2.

   sampling a color $c\sim {𝒰}_{L(u)\setminus \omega (N(u))}$,

3. 3.

   defining $\sigma$ by , and moving to the state $\sigma$.

Note that $L(u)\setminus \omega (N(u))$ is the set of available colors for $u$. These colors are in the list $L(u)$ but are not used by the coloring $\omega$ on the neighbors of $u$ so setting $\omega (u)$ to one of them yields a valid list coloring. This chain is reversible, and when $q\ge \mathrm{\Delta }+2$ it is ergodic [18, Exercises 4.1] with stationary distribution uniform on $\mathrm{\Omega }$.

For the purpose of constructing the couplings required by Theorem 3, let $\mathrm{\Gamma }$ be the weighted, directed graph on $\mathrm{\Omega }$ where $(\omega ,{\omega }^{\prime })$ is an edge if and only if the colorings $\omega ,{\omega }^{\prime }$ differ at exactly one vertex and let all edge weights be 1. From the proof of ergodicity [18] it follows that we can take $D=(\mathrm{\Delta }+1)n$ in Theorem 3 and define couplings as follows. Let $(\omega ,{\omega }^{\prime })\in E(\mathrm{\Gamma })$ and suppose that the colorings $\omega$ and ${\omega }^{\prime }$ differ at the vertex $v^{\ast }$. Sample $u\in V(G)$ uniformly at random and update the color of $u$ in both chains (intuitively, this decision helps the chains coalesce). That is, the distribution $\gamma$ of $(\sigma ,{\sigma }^{\prime })$ is defined by the Markov transition $(\omega ,{\omega }^{\prime })\stackrel{P_{\gamma }}{\mapsto }(\sigma ,{\sigma }^{\prime })$ itself defined by

1. 1.

   sampling a vertex $u\sim {𝒰}_{V(G)}$,

2. 2.

   sampling a pair of available colors $(a,b)$ from a distribution ${\gamma }_c$ such that

   $${\gamma }_c:=\underset{\begin{array}{c}{\gamma }^{\prime }\text{ is a coupling of }\\ {𝒰}_{L\left(u\right)\setminus \omega \left(N\left(u\right)\right)}\text{ and }{𝒰}_{L\left(u\right)\setminus {\omega }^{\prime }\left(N\left(u\right)\right)}\end{array}}{\arg \max }\underset{(a,b)\sim {\gamma }^{\prime }}{\mathrm{Pr}}(a=b)$$

   (1)

3. 3.

   defining $\sigma$ and ${\sigma }^{\prime }$ by updating the color of $u$ in each to $a$ and $b$ respectively:

   $\sigma (v)$

   ${\sigma }^{\prime }(v)$

   and moving to the state $(\sigma ,{\sigma }^{\prime })$.

Observe that ${\gamma }_c$ is defined as the coupling on the uniform distributions of available colors, ${𝒰}_{L(u)\setminus \omega (N(u))}$ and ${𝒰}_{L(u)\setminus {\omega }^{\prime }(N(u))}$, which maximizes the probability the colors are the same. The important property of this definition in terms of applying Theorem 3 is that this coupling minimizes the expectation of the discrete metric on the sample.

If $u\in N(v^{\ast })$ the sets of available colors for $u$ can be different making ${\gamma }_c$ nontrivial. In this case, let $C=\omega (N(u)\setminus \{v^{\ast }\})$ and note that the two sets of available colors are $A=(L(u)\setminus C)\setminus \{\omega (v^{\ast })\}$ and $B=(L(u)\setminus C)\setminus \{{\omega }^{\prime }(v^{\ast })\}$. We wish to couple ${𝒰}_A$ and ${𝒰}_B$ such that the probability of choosing the same color is maximized, and the best general coupling is not too hard to find.

Let $m=\max \{|A|,|B|\}$. We have $A\cap B=(L(u)\setminus C)\setminus \{\omega (v^{\ast }),{\omega }^{\prime }(v^{\ast })\}$. Checking the four cases according to whether each of $\omega (v^{\ast })$ and ${\omega }^{\prime }(v^{\ast })$ are in $L(u)\setminus C$, we observe that $|A\cap B|\ge m-1$. By Lemma 4, we can ensure that the two chains choose the same color with probability at least $1-1/m$. Considering the definitions of $A$ and $B$, we also have $m\ge q-\mathrm{\Delta }$. Returning to the analysis of the coupling $\gamma$ described above, we have

This comes from the facts that $\delta (\omega ,{\omega }^{\prime })=1$ by assumption, the probability $1/n$ that we successfully reduce the distance by $1$ in an update to $v^{\ast }$, and the probability of at most $\mathrm{\Delta }/n$ that we choose to update a neighbor of $v^{\ast }$, and in this case fail to choose the same color in the coupling of the color choice in each chain given by Lemma 4 (which occurs with probability at most $1/(q-\mathrm{\Delta })$ given that we update a neighbor of $v^{\ast }$). Set $\beta$ to the right-hand side above and solve for to obtain $q>2\mathrm{\Delta }$.

Well-known works that first studied this technique [17, 5, 18] give a similar proof, though Jerrum [17] manually constructed a coupling of the Markov chain and did not appeal to path coupling. With path coupling, it is slightly easier to study a variant of the Markov chain known as the “Metropolis Glauber dynamics” where the transition is defined slightly differently, though the same lower bound on $q$ is required in the argument for this chain.

Our argument for list packing follows the same outline as above using the heat-bath dynamics for list packings, but it is much harder to construct the coupling. In particular, we need an analogue of Lemma 4 for the much more intricate combinatorial setting of list packings. We describe this in the next subsection.

In this section we fix an $n$-vertex graph $G$ of maximum degree $\mathrm{\Delta }$, a $q$-list assignment $L$ of $G$, and let $\mathrm{\Omega }$ be the set of $L$-packings of $G$.

We consider heat-bath Glauber dynamics $ℳ=ℳ(G,L)$ for list packing. Given a state $\omega \in \mathrm{\Omega }$ and a vertex $u\in V(G)$, we say that a permutation $\rho$ in $S_q$ is available for $u$ in $\omega$ if setting ${\omega }_u$ to $\rho$ yields a valid list packing. Transitions of $ℳ$ are defined as follows. From state $\omega \in \mathrm{\Omega }$, choose vertex $u\in V(G)$ uniformly at random, choose an available permutation $\rho \in S_q$ uniformly at random, and let the new state be $\sigma$ given by ${\sigma }_u=\rho$ and ${\sigma }_v={\omega }_v$ for $v\ne u$. It is straightforward to check that this is a reversible Markov chain on $\mathrm{\Omega }$ with uniform stationary distribution. The question of ergodicity is less straightforward, though the standard argument for list coloring adapts easily. We require a simple corollary of Hall’s classic result on perfect matchings in bipartite graphs.

In this section we prove Lemmas 2 and 5. We first collect some results on auxiliary bipartite graphs.

Many natural questions remain unanswered. We have chosen to extend some of the most fundamental techniques for counting list colorings to list packings, but there are many more recent improvements to consider. Dyer and Greenhill [11] study a Markov chain on (list) colorings whose transitions are defined by properly recoloring both endpoints of a uniform random edge and show that its mixing time is less than that of Glauber dynamics studied in [17, 25]. The flip dynamics employed by Vigoda [26] for counting colorings is an important technique that gets significantly below the number of colors required by Jerrum’s approach. Extending Vigoda’s approach to list coloring was first done by Chen et al. [10], roughly 20 years after Vigoda’s breakthrough. Though they also surpassed a significant barrier at $11\mathrm{\Delta }/6$ colors related to 1-step contractions in Hamming distance of two colorings that differ at a vertex. The history of this problem suggests that further generalizations, e.g. to list packing may not be straightforward. While one can consider analogous dynamics for list packings and hope to reduce the bound on $q$ in Theorem 1, we do not have results showing the existence of list packings in graphs of maximum degree $\mathrm{\Delta }$ for fewer than $2\mathrm{\Delta }-2$ colors. In another direction, the use of more advanced Markov chain techniques to give perfect sampling of list packings could be interesting.

We finish with a natural conjecture on approximately counting list packings.

At the time of writing, we know of no reason that the lower bound on $q$ cannot be reduced to, say, $\mathrm{\Delta }+1$. The value $2\mathrm{\Delta }$ represents a significant barrier in the sense that the existence of a list packing when $q\ge 2\mathrm{\Delta }$ is an elementary consequence of Hall’s theorem (though arguably not entirely trivial).