Counting hypergraph colorings in the local lemma regime

Heng Guo, Chao Liao, Pinyan Lu, Chihao Zhang

Abstract

This research presents the first fully polynomial-time approximation scheme (FPTAS) and almost uniform sampler for counting colorings in $k$-uniform hypergraphs within the "local lemma regime." By departing from traditional Markov Chain Monte Carlo (MCMC) methods, the authors provide a robust framework to count and sample colorings even when the number of available colors is significantly smaller than the maximum degree of the hypergraph—a regime where standard algorithms typically fail due to state-space "freezing."

Introduction

The problem of counting and sampling proper $q$-colorings in a $k$-uniform hypergraph with maximum degree $\Delta$ is a cornerstone of combinatorial optimization. In a proper coloring, no hyperedge is monochromatic. While the Lovász Local Lemma (LLL) provides a powerful tool to guarantee the existence of such colorings when $q$ is roughly $\Delta^{1/(k-1)}$, the task of counting these colorings is significantly more complex.

Historically, researchers have relied on MCMC methods like Glauber dynamics. However, these methods generally require $q$ to be relatively large (typically $q > \Delta$) to ensure the Markov chain can move efficiently between valid colorings. When $q \ll \Delta$, the state space can become disconnected or "frozen," rendering MCMC ineffective. This paper addresses this challenge for general $k$-uniform hypergraphs without requiring restrictive structural assumptions like "simplicity."

Methodology

The authors build upon a deterministic framework introduced by Ankur Moitra (2017) for $k$-CNF formulas, extending it to the more complex domain of hypergraph colorings through several technical innovations:

1. Adaptive Coupling

To decouple the parameters $k$ and $\Delta$, the authors developed an adaptive coupling process. Unlike static marking arguments that require $k$ to be logarithmic in $\Delta$, this adaptive approach chooses vertices to couple on the fly. This ensures that marginal distributions remain close to uniform throughout the process, regardless of how $\Delta$ scales.

2. Linear Programming (LP) for Marginal Estimation

The algorithm estimates the marginal probability of a vertex being assigned a specific color by constructing a system of linear constraints. These constraints model the transition probabilities of the coupling process. By solving the resulting LP and employing binary search, the algorithm can accurately approximate marginals without traversing the entire state space.

3. {2,3}-Trees for Error Bounding

A critical component of the proof involves showing that "bad" colorings—those that might impede the coupling process—are sufficiently rare. The authors utilize a combinatorial structure known as a {2,3}-tree to perform a union bound over these events, demonstrating that they occur with exponentially small probability.

4. Self-Reduction

With a reliable method for estimating marginal probabilities, the authors apply standard self-reduction techniques to count the total number of colorings and use adaptive simulation to generate almost uniform samples.

Key Insights

  • Bypassing Connectivity: Because the algorithm relies on marginal estimation via LP rather than state-space exploration, it is immune to the "freezing" issues that plague MCMC. It can successfully count colorings even when the valid configurations are disconnected.
  • LLL as a Counting Tool: While the LLL is traditionally an existence proof, this work uses its conditions to prove that color distributions are "locally" almost uniform. This local uniformity is the engine that allows the coupling process to succeed.
  • Independence of Parameters: The adaptive approach proves that the local lemma regime for counting is reachable for any sufficiently large $k$, independent of the scaling of $\Delta$.

Results

The paper establishes two primary algorithmic breakthroughs for $k$-uniform hypergraphs:

  1. Counting (FPTAS): An algorithm exists to count $q$-colorings if $k \ge 28$ and $q > 357\Delta^{14/(k-14)}$.
  2. Sampling: An almost uniform sampler exists if $k \ge 28$ and $q > 931\Delta^{16/(k-16/3)}$.

These represent the first such results for general hypergraphs in the regime where $q \ll \Delta$. The algorithms run in time fully polynomial relative to the number of vertices $n$ and the error tolerance $1/\epsilon$.

Limitations and Future Work

The current requirements for $k$ ($k \ge 28$) and the large constants in the bounds for $q$ are likely artifacts of the proof technique rather than fundamental limits. Future research may tighten these bounds. Additionally, while this approach works for hypergraph colorings because partial assignments can generally be extended, generalizing "adaptive coupling" to broader Constraint Satisfaction Problems (CSPs) like $k$-SAT—where partial assignments often lead to contradictions—remains a significant open challenge.

Summary updated

BibTeX
@article{guo2019counting,
  author = {Heng Guo and Chao Liao and Pinyan Lu and Chihao Zhang},
  title = {{Counting hypergraph colorings in the local lemma regime}},
  journal = {SIAM Journal on Computing},
  year = {2019},
  url = {https://openreview.net/forum?id=REDRWc5aeC},
}
Figure