Algorithmic barriers from phase transitions

Introduction

For many random Constraint Satisfaction Problems (CSP), such as random graph coloring, random $k$-SAT, random Max $k$-SAT, and hypergraph 2-coloring, by now, we have asymptotically tight estimates for the largest constraint density for which typical instances have solutions (see ). At the same time, all known efficient algorithms for each problem fair very poorly, i.e., they stop finding solutions at constraint densities much lower than those for which we can prove that solutions exist. Adding insult to injury, the best known algorithm for each problem asymptotically fairs no better than certain extremely naive algorithms for the problem.

For example, it has been known for nearly twenty years that the following very simple algorithm will find a satisfying assignment of a random $k$-CNF formula with $m=rn$ clauses for $r=O(2^{k}/k)$: if there is a unit clause satisfy it; otherwise assign a random value to a random unassigned variable. While it is known that random $k$-CNF remain satisfiable for $r=\Theta(2^{k})$, no polynomial-time algorithm is known to find satisfying assignments for $r=(2^{k}/k)\cdot\omega(k)$ for some function $\omega(k)\to\infty$.

Similarly, for all $k\geq 3$, the following algorithm will $k$-color a random graph with average degree $d\leq k\ln k$: select a random vertex with fewest available colors left and assign it a random available color. While it is known that random graphs remains $k$-colorable for $d\sim 2\,k\ln k$, no polynomial-time algorithm is known that can $k$-color a random graph of average degree $(1+\epsilon)k\ln k$ for some fixed $\epsilon>0$ and arbitrarily large $k$. Equivalently, while it is trivial to color a random graph using twice as many colors as its chromatic number, no polynomial-time algorithm is known that can get by with $(2-\epsilon)\chi$ colors, for some fixed $\epsilon>0$.

Random $k$-SAT and random graph coloring are not alone. In fact, for nearly every random CSP of interest, the known results establish a completely analogous state of the art:

There is a trivial upper bound on the largest constraint density for which solutions exist.

There is a non-constructive proof, usually via the second moment method, that the bound from (1) is essentially tight, i.e., that solutions do exist for densities nearly as high as the trivial upper bound.

Some simple algorithm finds solutions up to a constraint density much below the one from (2).

No polynomial-time algorithm is known to succeed for a density asymptotically greater than that in (3).

In this paper we prove that this is not a coincidence. Namely, for random graph coloring, random $k$-SAT, and random hypergraph 2-coloring, we prove that the point where all known algorithms stop is precisely the point where the geometry of the space of solutions undergoes a dramatic change. This is known as a “dynamical” phase transition in statistical physics and our results establish rigorously for random CSPs a large part of the “1-step Replica Symmetry Breaking” hypothesis . Roughly speaking, this hypothesis asserts that while the set of solutions for low densities looks like a giant ball, at some critical point this ball shatters into exponentially many pieces that are far apart from one another and separated by huge “energy barriers”. Algorithms (even extremely simple ones) have no problem finding solutions in the “ball” regime, but no algorithm is known that can find solutions in the “error-correcting code” regime.

We believe that the presence of dynamical phase transitions in random CSPs is a very general phenomenon, whose qualitative characteristics should be problem-independent, i.e., universal. The fact that we can establish the exact same qualitative picture for a problem with binary constraints over $k$-ary variables (random graph $k$-coloring) and a problem with $k$-ary constraints over binary variables (hypergraph 2-colorability) certainly lends support to this notion. That said, we wish to emphasize that determining for each random CSP the location of its dynamical phase transition (as we do in this paper for the three problems mentioned, in order to show that the transition coincides with the demise of all known algorithms) requires non-trivial, problem-specific ideas and computations.

Perhaps the following is an intuitive model of how a dynamical phase transition comes about. In random graph coloring, rather than thinking of the number of available colors as fixed and the constraint density (number of edges) as increasing, imagine that we keep the constraint density fixed, but we keep decreasing the number of available colors. If we start with $q$ available colors where $q\gg\chi$, it is reasonable to imagine that the set of valid $q$-colorings, viewed as a subset of $\{1,2,\ldots,q\}^{n}$, has a nice “round” shape, the rounder the greater $q$ is relative to $\chi$. By the same token, when we restrict our attention to the set of those $q$-colorings that only use colors $\{1,2,\ldots,q-1\}$, we are taking a “slice’ of the set of $q$-colorings. With each slicing the connectivity of the set at hands deteriorates, until at some point the set shatters. For example, slicing the 2-dimensional unit sphere through the origin yields a circle, but slicing the circle, yields a pair of points.

We conclude the introduction with a few words about the technical foundation for our work. To prove the existence (and determine the location) of a dynamical phase transition one needs access to statistical properties of the uniform measure over solutions. A geometric way of thinking about this is as follows. Given a CSP instance, say a $k$-CNF formula with $m$ clauses chosen uniformly at random, consider the function $H$ on $\{0,1\}^{n}$ that assigns to each truth assignment the number of clauses it violates. In this manner, $H$ defines a “landscape” in which satisfying assignments correspond to valleys at sea-level. Understanding statistical properties of the uniform measure over solutions amounts to understanding “the view” one enjoys from such a valley, a probabilistically formidable task. As we discuss in Section 4, we can establish the following: the number of solutions of a random CSP is sufficiently concentrated around its exponentially large expectation for the view from a random sea-level valley to be “the same” as the view from an “artificial” valley. That is, from the valley that results by first selecting a random $\sigma\in\{0,1\}^{n}$ and then forming a random $k$-CNF formula, also with $m$ clauses, but now chosen uniformly among the clauses satisfied by $\sigma$, i.e., the view from the planted satisfying assignment in the planted model. This is a much easier view to understand and we believe that the “transfer” theorems we establish in this paper will significantly aid in the analysis of random CSPs.

Statement of Results

The height of a path $\sigma_{0},\sigma_{1},\ldots,\sigma_{t}\in D^{n}$ is $\max_{i}H(\sigma_{i})$. We say that $\sigma\in D^{n}$ is a solution of an instance $I$, if $H(\sigma)=0$. We will denote by $\mathcal{S}(I)$ the set of all solutions of an instance $I$. The clusters of an instance $I$ are the connected components of $\mathcal{S}(I)$. A region is a non-empty union of clusters.

The term cluster comes from physics. Requiring $\mbox{dist}(\sigma,\tau)=1$ to say that $\sigma,\tau$ are adjacent is somewhat arbitrary (but conceptually simplest) and a number of our results hold if one replaces 1 with $o(n)$.

We will be interested in distributions of CSP instances as the number of variables $n$ grows. The set $C=C_{n}$ will typically consist of all possible constraints of a certain type, e.g., the set of all $\binom{n}{k}$ possible hyperedges in the problem of 2-coloring random $k$-uniform hypegraphs. We let $I_{n,m}$ denote the set of all CSP instances with precisely $m$ distinct constraints from $C_{n}$ and we let $\mathcal{I}_{n,m}$ denote the uniform distribution on the set of all instances $I_{n,m}$. We will say that a sequence of events $\mathcal{E}_{n}$ holds with high probability (w.h.p.) if $\lim_{n\to\infty}\Pr[\mathcal{E}_{n}]=1$ and with uniformly positive probability (w.u.p.p.) if $\liminf_{n\to\infty}\Pr[\mathcal{E}_{n}]>0$. As per standard practice in the study of random structures, we will take the liberty of writing $\mathcal{I}_{n,m}$ to denote the underlying random variable and, thus, write things like “The probability that $\mathcal{S}(\mathcal{I}_{n,m})$…”

We say that the set of solutions of $\mathcal{I}_{n,m}$ shatters if there exist constants $\beta,\gamma,\zeta,\theta>0$ such that w.h.p. $\mathcal{S}(\mathcal{I}_{n,m})$ can be partitioned into regions so that:

The number of regions is at least $e^{\beta n}$.

Each region contains at most an $e^{-\gamma n}$ fraction of all solutions.

The Hamming distance between any two regions is at least $\zeta n$.

Every path between vertices in distinct regions has height at least $\theta n$.

Our first main result asserts that the space of solutions for random graph coloring, random $k$-SAT, and random hypergraph 2-colorability shatters and that this shattering occurs just above the largest density for which any polynomial-time algorithm is known to find solutions for the corresponding problem. Moreover, we prove that the space remains shattered until, essentially, the CSP’s satisfiability threshold. More precisely:

– A random graph with average degree $d$, i.e., $m=dn/2$, is w.h.p. $k$-colorable for $d\leq(2-\gamma_{k})k\ln k$, where $\gamma_{k}\to 0$. The best poly-time $k$-coloring algorithm w.h.p. fails for $d\geq(1+\delta_{k})k\ln k$, where $\delta_{k}\to 0$.

There exists a sequence $\epsilon_{k}\to 0$, such that the space of $k$-colorings of a random graph with average degree $d$ shatters for all

– A random $k$-CNF formula with $n$ variables and $rn$ clauses is w.h.p. satisfiable for $r\leq 2^{k}\ln 2-k$. The best poly-time satisfiability algorithm w.h.p. fails for $r>2^{k+1}/k$. In , non-rigorous, but mathematically sophisticated evidence is given that a different algorithm succeeds for $r=\Theta((2^{k}/k)\ln k)$, but not higher.

There exists a sequence $\epsilon_{k}\to 0$ such that the space of satisfying assignments of a random $k$-CNF formula with $rn$ clauses shatters for all

– A random $k$-uniform hypergraph with $n$ variables and $rn$ edges is w.h.p. 2-colorable for $r\leq 2^{k-1}\ln 2-\frac{3}{2}$. The best poly-time 2-coloring algorithm w.h.p. fails for $r>2^{k}/k$. In , non-rigorous, but mathematically sophisticated evidence is given that a different algorithm succeeds for $r=\Theta((2^{k}/k)\ln k)$, but not higher.

There exists a sequence $\epsilon_{k}\to 0$ such that the space of 2-colorings of a random $k$-uniform hypergraph with $rn$ edges shatters for all

As the notation in Theorems 2.1,2.2,2.3 is asymptotic in $k$, the stated intervals may be empty for small values of $k$. In this extended abstract we have not optimized the proofs to deliver the smallest values of $k$ for which the intervals are non-empty. Quick calculations suggest $k\geq 6$ for hypergraph 2-colorability, $k\geq 8$ for $k$-SAT, and $k\geq 20$ for $k$-coloring.

2 Rigidity

The regions mentioned in Theorems 2.1, 2.2 and 2.3 can be thought of as forming an error-correcting code in the solution-space of each problem. To make this precise we need to introduce the following definition and formalize the notion of “a random solution of a random instance”.

Given an instance $I$, a solution $\sigma\in\mathcal{S}(I)$ and a variable $v\in V$, we say that $v$ in $(I,\sigma)$:

Is $f(n)$-rigid, if every $\tau\in\mathcal{S}(I)$ such that $\tau(v)\neq\sigma(v)$ has $\mbox{dist}(\sigma,\tau)\geq f(n)$.

Is $f(n)$-loose, if for every $j\in D$, there exists $\tau\in\mathcal{S}(I)$ such that $\tau(v)=j$ and $\mbox{dist}(\sigma,\tau)\leq f(n)$.

We will prove that while before the phase transition, in a typical solution, every variable is loose, after the phase transition nearly every variable is rigid. To formalize the notion of a random/typical solution, recall that $I_{n,m}$ denotes the set of all instances with $m$ constraints over $n$ variables and let $\Lambda=\Lambda_{n,m}$ denote the set of all instance–solution pairs, i.e., $\Lambda_{n,m}=\{(I,\sigma):I\in{I}_{n,m},\,\sigma\in\mathcal{S}(I)\}$. We let $\mathcal{U}=\mathcal{U}_{n,m}$ be the probability distribution induced on $\Lambda_{n,m}$ by the following:

Choose an instance $I\in I_{n,m}$ uniformly at random.

If $\mathcal{S}(I)\neq\emptyset$, select $\sigma\in\mathcal{S}(I)$ uniformly at random.

We will refer to instance-solution pairs generated according to $\mathcal{U}_{n,m}$ as uniform instance-solution pairs. We note that although the definition of uniform pairs allows for $\mathcal{S}(I)$ to be typically empty, i.e., to be in the typically unsatisfiable regime, we will only employ the definition for constraint densities such that w.h.p. $\mathcal{S}(I)$ contains exponentially many solutions. Hence, our liberty in also using the term a “typical” solution.

Let $(I,\sigma)$ be a uniform instance-solution pair where:

$I$ is a graph with $dn/2$ edges, where $d$ is as in (1), and $\sigma$ is a $k$-coloring of $I$, or,

$I$ is a $k$-CNF formula with $rn$ clauses, where $r$ is as in (2), and $\sigma$ is a satisfying assignment of $I$, or,

$I$ is a $k$-uniform hypergraph with $rn$ edges, where $r$ is as in (3), and $\sigma$ is a 2-coloring of $I$.

W.h.p. the number of rigid variables in $(I,\sigma)$ is at least $\gamma_{k}n$, for some sequence $\gamma_{k}\to 1$.

Theorem 2.4 is tight since for every finite constraint density, a random instance w.h.p. has $\Omega(n)$ variables that are not bound by any constraint.

The picture drawn by Theorem 2.4, whereby nearly all variables are rigid in typical solutions above the dynamical phase transition, is in sharp contrast with our results for densities below the transition for graph coloring and hypergraph 2-colorability. While we believe that an analogous picture holds for $k$-SAT, see Conjecture 1, for technical reasons we cannot establish this presently. (We discuss the additional difficulties imposed by random $k$-SAT in Section 4.)

Let $(I,\sigma)$ be a uniform instance-solution pair where:

$I$ is a graph with $dn/2$ edges, where $d\leq(1-\epsilon_{k})k\ln k$, and $\sigma$ is a $k$-coloring of $I$, or,

$I$ is a $k$-uniform hypergraph with $rn$ edges, where $r\leq(1-\epsilon_{k})(2^{k-1}/k)\ln k$, and $\sigma$ is a 2-coloring of $I$.

There exists a sequence $\epsilon_{k}\rightarrow 0$ such that w.h.p. every variable in $(I,\sigma)$ is $o(n)$-loose.

We note that in fact, for all $d$ and $r$ as in Theorem 2.5, w.u.p.p. $(I,\sigma)$ is such that changing the color of any vertex to any color only requires changing the color of $O(\log n)$ other vertices.

Let $(I,\sigma)$ be a uniform instance-solution pair where $I$ is a $k$-CNF formula with $rn$ clauses, where $r\leq(1-\epsilon_{k})(2^{k}/k)\ln k$, and $\sigma$ is a satisfying assignment of $I$. There exists a sequence $\epsilon_{k}\rightarrow 0$ such that w.h.p. every variable in $(I,\sigma)$ is $o(n)$-loose.

Background and Related Work

Attempts for a “quick improvement” upon either of the naive algorithms mentioned in the introduction for satisfiability/graph coloring, stumble upon the following general fact. Given a CSP instance, consider the bipartite graph in which every variable is adjacent to precisely those constraints in which it appears, known as the factor graph of the instance. For random formulas/graphs, factor graphs are locally tree-like, i.e., for any arbitrarily large constant $D$, the depth-$D$ neighborhood of a random vertex is a tree w.h.p. In other words, locally, random CSPs are trivial, e.g., random graphs of any finite average degree are locally 2-colorable. Moreover, as the constraint density is increased, the factor graphs of random CSPs get closer and closer to being biregular, so that degree information is not useful either. Combined, these two facts render all known algorithms impotent, i.e., as the density is increased, their asymptotic performance matches that of trivial algorithms.

In , Mézard, Parisi, and Zecchina proposed a new satisfiability algorithm called Survey Propagation (SP) which performs extremely well experimentally on instances of random 3-SAT. This was very surprising at the time and allowed for optimism that, perhaps, random $k$-SAT instances might not be so hard. Moreover, SP was generalized to other problems, e.g., $k$-coloring and Max $k$-SAT . An experimental evaluation of SP for values of $k$ even as small as 5 or 6 is already somewhat problematic, but to the extent it is reliable it strongly suggests that SP does not find solutions for densities as high as those for which solutions are known to exist. Perhaps more importantly, it can be shown that for densities at least as high as $2^{k}\ln 2-k$, if SP can succeed at its main task (approximating the marginal probability distribution of the variables with respect to the uniform measure over satisfying assignments), so can a much simpler algorithm, namely Belief Propagation (BP), i.e., dynamic programming on trees.

The trouble is that to use either BP or SP to find satisfying assignments one sets variables iteratively. So, even if it is possible to compute approximately correct marginals at the beginning of the execution (for the entire formula), this can stop being the case after some variables are set. Concretely, in , Montanari et al. showed that (even within the relatively generous assumptions of statistical physics computations) the following Gibbs-sampling algorithm fails above the $(2^{k}/k)\ln k$ barrier, i.e., step 2 below fails to converge after only a small fraction of all variables have been assigned a value:

Compute the marginal distribution of $v$ using Belief Propagation.

Set $v$ to $\{0,1\}$ according to the computed marginal distribution; simplify the formula; go to step 1.

2 Relating the Uniform and the Planted Model.

The idea of deterministically embedding a property inside a random structure is very old and, in general, the process of doing this is referred to as “planting” the property. In our case, we plant a solution $\sigma$ in a random CSP, by only including constraints compatible with $\sigma$. Juels and Peinado were perhaps the first to explore the relationship between the planted and the uniform model and they did so for the clique problem in dense random graphs $G_{n,1/2}$, i.e., where each edge appears independently with probability 1/2. They showed the distribution resulting from first choosing $G=G_{n,1/2}$ and then planting a clique of size $(1+\varepsilon)\log_{2}n$ is very close to $G_{n,1/2}$ and suggested this as a scheme to obtain a one-way-function. Since the planted clique has size only $(1+\varepsilon)\log_{2}n$, the basic argument in is closely related to subgraph counting. In contrast, the objects under consideration in our work ($k$-colorings, satisfying assignments, etc.) have an immediate impact on the global structure of the combinatorial object being considered, rather than just being local features, such as a clique on $O(\log n)$ vertices.

Coja-Oghlan, Krivelevich, and Vilenchik proved that for constraint densities well above the threshold for the existence of solutions, the planted model for $k$-coloring and $k$-SAT is equivalent to the uniform distribution conditional on the (exponentially unlikely) existence of at least one solution. In this conditional distribution as well as in the high-density planted model, the geometry of the solution space is very simple, as there is precisely one cluster of solutions.

3 Solution-space Geometry

In the first steps were made towards understanding the solution-space geometry of random $k$-CNF formulas by proving the existence of shattering and the presence of rigid variables for $r=\Theta(2^{k})$. This was a far cry from the true $r\sim(2^{k}/k)\ln k$ threshold for the onset of both phenomena, as we establish here. Besides the quantitative aspect, there is also a fundamentally important difference in the methods employed in vs. those employed here. In those works, properties were established by taking a union bound over all satisfying assignments. It is not hard to show that the derived results are best possible using those methods and, in fact, there is good reason to believe that the results are genuinely tight, i.e., that for densities $o(2^{k})$ the derived properties simply do not hold for all satisfying assignments. Here, we instead establish a systematic connection between the planted model and the process of sampling a random solution of a random instance. This argument allows us to analyze “typical” solutions while allowing for the possibility that a (relatively small, though exponential) number of “atypical” solutions exist. Therefore, we are for the first time in a position to analyze the extremely complex energy landscape of below-threshold instances of random CSPs, and to estimate quantities that appeared completely out of reach prior to this work.

Our Point of Departure: Symmetry, Randomness and Inversion

As mentioned, the results in this paper are enabled by a set of technical lemmas that allow one to reduce the study of “random solutions of random CSP instances” to the study of “planted CSP solutions”. The conceptual origin of these lemmas can be traced to the following humble observation.

Let $M$ be an arbitrary -$1$ matrix with the property that all its rows have the same number of 1s and all its columns have the same the number of 1s. A moment’s reflection makes it clear that for such a matrix, both of the following methods select a uniformly random 1 from the entire matrix:

Select a uniformly random column and then a uniformly random 1 in that column.

Select a uniformly random row and then a uniformly random 1 in that row.

An example of how we employ this fact for random CSPs is as follows. Let $\mathcal{F}$ be the set of all $k$-CNF formulas with $n$ variables and $m$ distinct clauses (chosen among all $2^{k}\binom{n}{k}$ possible $k$-clauses). Say that $\sigma\in\{0,1\}^{n}$ NAE-satisfies a formula $F\in\mathcal{F}$ if under $\sigma$, every clause of $F$ has at least one satisfied and at least one falsified literal. Let $M$ be the $2^{n}\times|\mathcal{F}|$ matrix where$M_{\sigma,F}=1$ iff $\sigma\in\{0,1\}^{n}$ NAE-satisfies $F$. By the symmetry of $\mathcal{F}$, it is clear that all rows of $M$ have the same number of 1s. Imagine, for a moment, that the same was true for all columns. Then, a uniformly random solution of a uniformly random instance would be distributed exactly as a “planted” instance-solution pair: first select $\sigma\in\{0,1\}^{n}$ uniformly at random; then select $m$ distinct clauses uniformly at random among all $2^{k-1}\binom{n}{k}$ clauses NAE-satisfied by $\sigma$.

Our contribution begins with the realization that exact row- and column-balance is not necessary. Rather, it is enough for the 1s in $M$ to be “well-spread”. More precisely, it is enough that the marginal distributions induced on the rows and columns of $M$ by selecting a uniformly random 1 from the entire matrix are both “reasonably close to” uniform. For example, assume we can prove that $\Omega(|\mathcal{F}|)$ columns of $M$ have $\Theta(f(n))$ 1s, where $f(n)$ is the average number of 1s per column. Indeed, this is precisely the kind of property implied by the success of the second moment method for random NAE-$k$-SAT . Under this assumption, proving that a property holds w.u.p.p. for a uniformly random solution of a uniformly random instance, reduces to proving that it holds w.h.p. for the planted solution of a planted instance, a dramatically simpler task.

There is a geometric intuition behind our transfer theorems which is more conveniently described when every constraint is included independently with the same probability $p$, i.e., we take $p=m/\left(2^{k}\binom{n}{k}\right)$. For all $k\geq 3$ and $m=rn$, it was shown in that the resulting instances w.u.p.p. have exponentially many solutions for $r\leq 2^{k-1}\ln 2-3/2$. Consider now the following way of generating planted NAE $k$-SAT instances. First, select a formula $F$ by including each clause with probability $p$, exactly as above. Then, select $\sigma\in\{0,1\}^{n}$ uniformly at random and remove from $F$ all constraints violated by $\sigma$. Call the resulting instance $F^{\prime}$. Our results say that as long as $q\equiv r(1-2^{-k+1})\leq 2^{k-1}\ln 2-3/2$, the instance $F^{\prime}$ is “nearly indistinguishable” from a uniform instance created by including each clause with probability $q$. (We will make this statement precise shortly.)

To prove our transfer theorems we instantiate this idea for random graph $k$-coloring, random $k$-uniform hypergraph $2$-coloring, and random $k$-SAT. For this, a crucial step is deriving a lower bound on the number of solutions of a random instance. For example, in the case of random graph $k$-coloring, we prove that the number of $k$-colorings, $|\mathcal{S}(I_{n,m})|$, for a random graph with $n$ vertices and $m$ edges is “concentrated” around its expectation in the sense that w.h.p.

To prove this, we use the upper bound on the second moment $\mathbf{E}\left[{|\mathcal{S}(I_{n,m})|^{2}}\right]$ from to show that w.u.p.p. $|\mathcal{S}(I_{n,m})|=\Omega(\mathbf{E}|\mathcal{S}(I_{n,m})|)$. Then, we perform a sharp threshold analysis, using theorems of Friedgut , to prove that (4) holds, in fact, with high probability. A similar approach applies to hypegraph $2$-coloring.

The situation for random $k$-SAT is more involved. Indeed, we can prove that the number of satisfying assignments is not concentrated around its expectation in the sense of (4). This problem is mirrored by the fact that the second moment of the number of satisfying assignments exceeds the square of the first moment by an exponential factor (for any constraint density). Nonetheless, letting $F_{k}(n,m)$ denote a uniformly random $k$-CNF formula with $n$ variables and $m$ clauses, combining techniques from with a sharp threshold analysis, we can derive a lower bound on the number of satisfying assignments that holds w.h.p., namely $n^{-1}\ln|\mathcal{S}(F_{k}(n,m))|\geq n^{-1}\ln\mathbf{E}|\mathcal{S}(F_{k}(n,m))|-\phi(k)$, where $\phi(k)\rightarrow 0$ exponentially with $k$. This estimates allows us to approximate the uniform model by the planted model sufficiently well in order to establish Theorems 2.2 and 2.4.

Proof sketches

Due to the space constraints, in the remaining pages we give proof sketches of our results for $k$-coloring, to offer a feel of the transfer theorems and of the style of the arguments one has to employ given those theorems (actual proofs appear in the Appendix). The proofs for hypergraph 2-coloring are relatively similar, as it is also a “symmetric” CSP and the second moment methods works on its number of solutions. For $k$-SAT, though, a significant amount of additional work is needed, as properties must be established with exponentially small error probability to overcome the large deviations in the number of satisfying assignments (proofs appear in the Appendix).

We consider a fixed number $\varepsilon>0$ and assume that $k\geq k_{0}$ for some sufficiently large $k_{0}=k_{0}(\varepsilon)$. We denote $\{1,\ldots,k\}$ as $\left[{k}\right]$. We are interested in the probability distribution $\mathcal{U}_{n,m}$ on $\Lambda_{n,m}$ resulting from first choosing a random graph $G=G(n,m)$ and then a random $k$-coloring of $G$ (if one exists). To analyze this distribution, we consider the distribution $\mathcal{P}_{n,m}$ on $\Lambda_{n,m}$ induced by following expermient.

Generate a uniformly random $k$-partition $\sigma\in\left[{k}\right]^{n}$.

Generate a graph $G$ with $m$ edges chosen uniformly at random among the edges bicolored under $\sigma$.

The distribution $\mathcal{P}_{n,m}$ is known as the planted model.

Suppose that $d=2m/n\leq(2-\varepsilon)k\ln k$. There exists a function $f(n)=o(n)$ such that the following is true. Let $\mathcal{D}$ be any graph property such that $G(n,m)$ has $\mathcal{D}$ with probability $1-o(1)$, and let $\mathcal{E}$ be any property of pairs $(G,\sigma)\in\Lambda_{n,m}$. If for all sufficiently large $n$

2 Loose Variables Below the Transition

Suppose that $d\leq(1-\varepsilon)k\ln k$. Recall that a graph with vertex set $V$ is said to be $\zeta$-choosable if for any assignments of color lists of length at least $\zeta$ to the elements of $V$, there is a proper coloring in which every vertex receives a color from its list. To prove Theorem 2.5, we consider the property $\mathcal{E}$ that all vertices are $o(n)$-loose and the following condition $\mathcal{D}$:

For any set $S\subset V$ of size $|S|\leq g(n)$ the subgraph induced on $S$ is $4$-choosable.

Here $g(n)$ is some function such that $f(n)\ll g(n)=o(n)$, where $f(n)$ is the function from Theorem 5.1. A standard argument shows that a random graph $G(n,m)$, where $m=O(n)$, satisfies $\mathcal{D}$ w.h.p.

By Theorem 5.1, we are thus left to establish (5). Let $\sigma\in\left[{k}\right]^{n}$ be a uniformly random $k$-partition, and let $G$ be a random graph with $m$ edges such that $\sigma$ is a $k$-coloring of $G$. Since $\sigma$ is uniformly random, we may assume that the color classes $V_{i}=\sigma^{-1}(i)$ satisfy $|V_{i}|\sim n/k$. Let $v_{0}\in V$ be any vertex, and let $l\not=\sigma(v_{0})$ be the “target color” for $v_{0}$. Our goal is to find a coloring $\tau$ such that $\tau(v_{0})=l$ and $\mbox{dist}(\sigma,\tau)\leq g(n)$.

If $v$ has no neighbor in $V_{l}$, then we can just assign this color to $v_{0}$. Otherwise, we run the following process. In the course of the process, every vertex is either awake, dead, or asleep. Initially, all the neighbors of $v_{0}$ in $V_{l}$ are awake, $v$ is dead, and all other vertices are asleep. In each step of the process, pick an awake vertex $w$ arbitrarily and declare it dead (if there is no awake vertex, terminate the process). If there are at least five colors $c_{1}(w),\ldots,c_{5}(w)$ available such that $w$ has no neighbor in $V_{c_{i}(w)}$, then we do nothing. Otherwise, we pick five colors $c_{1}(w),\ldots,c_{5}(w)$ randomly and declare all asleep neighbors of $w$ in $V_{c_{j}(w)}$ awake for $1\leq j\leq 5$.

With probability at least $1-\exp(-f(n))$ there are at most $g(n)$ dead vertices when the process terminates.

The proof of Lemma 1 is based on relating our process to a subcritical branching process. The basic insight here is that when $d<(1-\varepsilon)k\ln k$ it is very likely that a vertex $w$ has five immediately available colors. More precisely, for any $w$ the number of neighbors in any class $V_{i}$ with $i\not=\sigma(w)$ is asymptotically Poisson with mean $(1+o(1))\frac{2m}{(k-1)n}\leq(1-\varepsilon+o(1))\frac{k\ln k}{k-1}$. Hence, the probability that $w$ does not have a neighbor in $V_{i}$ is about $k^{\varepsilon-1}$. As there are $k$ colors in total, we expect about $(k-1)^{\varepsilon}$ colors available for $w$, i.e., a lot.

To obtain a new coloring $\tau$ in which $v_{0}$ takes color $l$ we consider the set $D$ of all dead vertices. We let $\tau(u)=\sigma(u)$ for all $u\in V\setminus D$. Moreover, conditioning on the event $\mathcal{D}$, we can assign to each $w\in D$ a color from the list $\{c_{1}(w),\ldots,c_{5}(w)\}\setminus\{l\}$. Thus, the new coloring $\tau$ differs from $\sigma$ on at most $|D|\leq g(n)=o(n)$ vertices.

3 Rigid Variables Above the Transition

Suppose that $d\geq(1+\varepsilon)k\ln k$. To prove Theorem 2.4 for coloring we apply Theorem 0.A.1 as follows. We let $\alpha,\beta>0$ be sufficiently small numbers and denote by $\mathcal{E}$ the following property of a pair $(G,\sigma)\in\Lambda_{n,m}$:

Also, we let $\mathcal{D}$ be the property that the maximum degree is at most $(\ln n)^{2}$.

We shall prove that for a pair $(G,\sigma)$ chosen from $\mathcal{U}_{n,m}$ a subgraph $G_{*}$ as in (6) exists w.h.p. If that is so, then every vertex in $G_{*}$ has at least one neighbor in every color class other than its own. Therefore, it is impossible to just assign a different color to any vertex in $G_{*}$. In fact, since all vertices in $G_{*}$ have a lot (namely, at least $\beta\ln k$) of neighbors with every other color, the expansion properties of the random graph $G(n,m)$ imply that recoloring any vertex $v$ in $G_{*}$ necessitates the recoloring of at least $n/(k\ln k)$ further vertices. Loosely speaking, the conflicts resulting from recoloring $v$ spread so rapidly that we necessarily end up recoloring a huge number of vertices. Thus, all vertices in $G_{*}$ are $n/(k\ln k)$-rigid. Note that we can not hope for much better, as we can always recolor $v$ by swapping two color classes, i.e., $\sim 2n/k$ vertices.

To prove the existence of the subgraph $G_{*}$, we establish the following.

Condition (5) holds for $\mathcal{D}$ and $\mathcal{E}$ as above.

To obtain Lemma 2, let $(G,\sigma)\in\Lambda_{n,m}$ be a random pair chosen from the distribution $\mathcal{P}_{n,m}$. We may assume that $|\sigma^{-1}(i)|\sim n/k$ for all $i$. To obtain the graph $G_{*}$, we perform a “stripping process”. As a first step, we obtain a subgraph $H$ by removing from $G$ all vertices that have fewer than $\gamma\ln k$ neighbors in any color class other than their own. If $\gamma=\gamma(\varepsilon)$ is sufficiently small, then the expected number of vertices removed in this way is less than $nk^{-\delta}$ for a $\delta>0$, because for each vertex $w$ the expected number of neighbors in another color class is bigger than $(1+\varepsilon)\ln k$. Then, we keep removing vertices from $H$ that have “a lot” of neighbors outside of $H$. Given the event $\mathcal{D}$, we then show that with probabiltiy $1-\exp(-\Omega(n))$ the final result of this process is a subgraph $G_{*}$ that satisfies (6).

4 Proof of Theorem 2.1

Theorem 2.1 concerns the “view” from a random coloring $\sigma$ of $G(n,m)$. Basically, our goal is to show that only a tiny fraction of all possible colorings are “visible” from $\sigma$, i.e., $\sigma$ lives in a small, isolated valley. To establish the theorem, we need a way to measure how “close” two colorings $\sigma,\tau$ are. The Hamming distance is inappropriate here because two colorings $\sigma,\tau$ can be at Hamming distance $n$, although $\tau$ simply results from permuting the color classes of $\sigma$, i.e., although $\sigma$ and $\tau$ are essentially identical. Instead, we shall use the following concept. Given two coloring $\sigma,\tau$, we let $M_{\sigma,\tau}=(M^{ij}_{\sigma,\tau})_{1\leq i,j\leq k}$ be the matrix with entries

To measure how close $\tau$ is to $\sigma$ we let

be the squared Frobenius norm of $M_{\sigma,\tau}$. Observe that this quantity reflects the probability that a single random edge is monochromatic under both $\sigma$ and $\tau$, i.e., the correlation of $\sigma$ and $\tau$, precisely as desired. Hence, $f_{\sigma}$ is a map from the set $\left[{k}\right]^{n}$ of $k$-partitions to the interval $\left[{k^{-2},f_{\sigma}(\sigma)}\right]$, where $f_{\sigma}(\sigma)\geq k^{-1}$. Thus, the larger $f_{\sigma}(\tau)$, the more $\tau$ resembles $\sigma$. Furthermore, for a fixed $\sigma\in\mathcal{S}(G)$ and a number $\lambda>0$ we let

In order to show that $\mathcal{S}(G_{n,m})$ with $m=rn$ decomposes into exponentially many regions, we employ the following lemma.

Suppose that $r>(\frac{1}{2}+\varepsilon_{k})k\ln k$. There are numbers $k^{-2}<y_{1}<y_{2}<k^{-1}$ and $\lambda,\gamma>0$ such that with high probability a pair $(G,\sigma)\in\Lambda_{n,m}$ chosen from the distributoin $\mathcal{U}_{n,m}$ has the following two properties.

For all $x\in\left[{y_{1},y_{2}}\right]$ we have $g_{\sigma,G,\lambda}(x)=0$.

The number of colorings $\tau\in\mathcal{S}(G)$ such that $f_{\sigma}(\tau)>y_{2}$ is at most $\exp(-\gamma n)\cdot|\mathcal{S}(G)|$.

Let $G=G_{n,m}$ be a random graph and call $\sigma\in\mathcal{S}(G)$ good if both (1) and (2) hold. Then Lemma 3 states that w.h.p. a $1-o(1)$-fraction of all $\sigma\in\mathcal{S}(G)$ are good. Hence, to decompose $\mathcal{S}(G)$ into regions, we proceed as follows. For each $\sigma\in\mathcal{S}(G)$ we let $\mathcal{C}_{\sigma}=\{\tau\in\mathcal{S}(G):f_{\sigma}(\tau)>y_{2}\}.$ Then starting with the set $S=\mathcal{S}(G)$ and removing iteratively some $\mathcal{C}_{\sigma}$ for a good $\sigma\in S$ yields an exponential number of regions. Furthermore, each such region $\mathcal{C}_{\sigma}$ is separated by a linear Hamming distance from the set $\mathcal{S}(G)\setminus\mathcal{C}_{\sigma}$, because $f_{\sigma}$ is “continuous” with respect to $n^{-1}\times$Hamming distance. Thus, Theorem 2.1 follows from Lemma 3.

Finally, by Theorem 5.1, to prove Lemma 3 it is sufficient to show the following.

Suppose that $r>(\frac{1}{2}+\varepsilon_{k})k\ln k$. There are $k^{-2}<y_{1}<y_{2}<k^{-1}$ and $\lambda,\gamma>0$ such that with probability at least $1-\exp(-\Omega(n))$ a pair $(G,\sigma)\in\Lambda_{n,m}$ chosen from the distributoin $\mathcal{P}_{n,m}$ has the two properties stated in Lemma 3.

The proof of Lemma 4 is based on the “first moment method”. That is, for any $k^{-2}<y<k^{-1}$ we compute the expected number of assignments $\tau\in\left[{k}\right]^{n}$ such that $f_{\sigma}(\tau)=y$ and $H(\tau)\leq\lambda n$. This computation is feasible in the planted model and yields similar expressions as encountered in in the course of computing the second moment of the number of $k$-colorings. Therefore, we can show that the expected number of such assignments $\tau$ is exponentially small for a regime $y_{1}<y<y_{2}$, whence Lemma 21 follows from Markov’s inequality.

References

Appendix 0.A Graph coloring

In this section we consider a fixed number $\varepsilon>0$ and assume that $k\geq k_{0}$ for some sufficiently large $k_{0}=k_{0}(\varepsilon)$. We are interested in the probability distribution $\mathcal{U}_{n,m}$ on $\Lambda_{n,m}$. To analyze this distribution, we consider the distribution $\mathcal{P}_{n,m}$ on $\Lambda_{n,m}$ induced by following expermient (“planted model”).

Generate a uniformly random $k$-partition $\sigma\in\left[{k}\right]^{n}$.

Generate a graph $G$ with $m$ edges chosen uniformly at random among the edges bicolored under $\sigma$.

Suppose that $d=2m/n<(2-\varepsilon)k\ln k$. There exists a function $f(n)=o(n)$ such that the following is true. Let $\mathcal{D}$ be any graph property such that $G(n,m)$ has $\mathcal{D}$ with probability $1-o(1)$, and let $\mathcal{E}$ be any property of pairs $(G,\sigma)\in\Lambda_{n,m}$. If for all sufficiently large $n$ we have

For a given assignment $\sigma\in\left[{k}\right]^{n}$ we let $G(\sigma)$ be the set of all graphs with $m$ edges for which $\sigma$ is a proper coloring. Then it is immediate that

Let $\gamma>0$ be sufficiently small. Moreover, let $n_{i}=|\sigma^{-1}(i)|$, $\delta_{i}=n_{i}-n/k$, and $N=(1-k^{-1})\binom{n}{2}$. Then $\sum_{i}\delta_{i}=0$. Therefore,

Since for a random $\sigma$ the numbers $n_{i}$ are multinomially distributed, with probability $\Omega(1)$ we have $|n_{i}-\frac{n}{k}|<\sqrt{\gamma n/k}$. Hence, letting $N(\sigma)=\sum_{i<j}n_{i}n_{j}$, we conclude that there is a constant $\rho>0$ such that

Thus, by Stirling’s formula with probability at least $\rho$ we have

Since $N=\Omega(n^{2})$ and $m=O(n)$, in the case $N(\sigma)\geq N-\gamma n$ we have

We have $|\Lambda_{n,m}|\geq\rho^{2}k^{n}\lambda$.

because $|G(\sigma)|\leq\lambda$ for all $\sigma$. Hence, Corollary 1 yields

There is a function $f(n)=o(n)$ such that $|\mathcal{S}(G_{n,m})|\geq\exp(-f(n))\mu$ with high probability.

Since $f(n)=o(n)$, this contradicts Lemma 6. ∎

A.2 Proof of Lemma 7

To prove Lemma 7, we combine the second moment argument from with a sharp threshold argument. Let $G=G(n,m)$ be a random graph and let $X$ be the number of balanced colorings of $G$, i.e., colorings $\sigma\in\left[{k}\right]^{n}$ such that $|\sigma^{-1}(i)-n/k|\leq 1$ for all $1\leq i\leq k$. Recall that $\mathcal{S}(G)$ denotes the set of all $k$-colorings of $G$. A direct computation involving Stirling’s formula shows that

In addition, [4, Section 3] shows that there is a constant $C=C(k)$ such that

Applying the Paley-Zigmund inequality, we thus conclude that there is a number $\alpha=\alpha(k)>0$ such that

where $r=m/n$. Thus, we obtain the following.

To complete the proof of Lemma 7, we combine Lemma 8 with a sharp threshold result. Let $\mathcal{A}_{\xi}$ be the property that a graph $G$ on $n$ vertices has less than $\xi^{n}$ $k$-colorings.

For any fixed $\xi>0$ the property $\mathcal{A}_{\xi}$ has a sharp threshold. That is, there is a sequence $r_{n}$ such that for any $\varepsilon>0$ we have

We shall prove Lemma 9 in Appendix 0.A.3. Lemma 7 is an immediate consequence of Lemmas 8 and 9.

A.3 Proof of Lemma 9

The property $\mathcal{A}_{\xi}$ is monotone under the addition of edges. Therefore, it is sufficient to prove that $\mathcal{A}_{\xi}$ has a sharp threshold in the random graph $G(n,p)$, in which edges are added with probability $p$ independently. Let $\mathcal{N}=\xi^{n}$. The argument builds upon . We denote the set of $k$-colorings of a graph $G$ by $\mathcal{S}(G)$.

Let $\omega$ be a (very) slow growing function of $n$. Moreover, let $\mathcal{E}_{i}$ be the event that the first $i$ constraints: “$v_{j}$ must not receive color $c_{j}$” for $1\leq j\leq i$, cause the number of $k$-colorings to be at most $\mathcal{N}^{\prime}$. Then given that $G=G(n,p)$ has more than $\mathcal{N}^{\prime}$ $k$-colorings (i.e., coditional on the event $\bar{\mathcal{E}}_{0}$), the probability of $\mathcal{E}_{M}$ is at least $\frac{1}{2}$. Hence, conditional on $\bar{\mathcal{E}}_{0}$, we have

Since for each of the $y$ colorings the probability that a new random edge spoils this coloring is $k^{-1}$, we can reduce the number of colorings to at most $\mathcal{N}^{\prime}$ by adding $\omega$ random edges (use Markov’s inequality).

Now, note that instead of first imposing the $M-1$ constraints $w_{1},\ldots,w_{M-1}$ and then adding the random edges as in Cases 1 and 2 we could first add a set of $2\omega^{10}$ random edges to $G(n,p)$. As $\omega^{10}$ is of smaller order than the standard deviation of the number of edges of $G(n,p)$, the resulting distribution is within $o(1)$ from the originial distribution $G(n,p)$ in total variation distance. Therefore, we conclude that actually just imposing the $M-1$ constraints $w_{1},\ldots,w_{M-1}$ suffices to increase the probability of having $\leq\mathcal{N}^{\prime}$ $k$-colorings to $1-\tau/2+o(1)$. ∎

Applying the lemma $M$ times, we can reduce the number of constraints that is necessary to reduce the number of colorings to $\leq\mathcal{N}^{\prime}$ to . ∎

To prove that $\mathcal{A}_{\xi}$ has a sharp threshold, we assume for contratiction that this is not so. Hence, there exists an edge probability $p^{*}$ such that the probability that $G_{n,p^{*}}$ has $\mathcal{A}_{\xi}$ is exactly equal to $1-t$ for a small $t>0$. Further, by [15, Theorem 2.4] there exists a fixed graph $R$ on $r$ vertices such that with probability $>1-t/3$ the following is true. If we first pick $G=G_{n,p^{*}}$ and then insert a random copy of $R$ into $G$, then the resulting graph has $\mathcal{A}_{\xi}$. Furthermore, this graph $R$ is $k$-colorable. In fact, by monotonicity we may assume that $R$ is uniquely $k$-colorable. The experiment of inserting a random copy of $R$ into $G_{n,p^{*}}$ is actually equivalent to the following (because $G_{n,p^{*}}$ is symmetric with respect to vertex permutations). We let $G_{R}$ denote a random graph obtained by first inserting a copy of $R$ into the first $r$ vertices $v_{1},\ldots,v_{r}$, and then adding edges with probability $p^{*}$ independently (among all $n$ vertices $v_{1},\ldots,v_{n}$). Then the probability that $G_{R}$ has $\mathcal{A}_{\xi}$ is at least $1-t/3$. Hence,

Let $\hat{G}$ signify the subraph of $G_{R}$ induced on the $n-r$ vertices $v_{r+1},\ldots,v_{n}$. Then $\hat{G}=G_{n-r,p^{*}}$, and (9) implies that

Furthermore, we can relate the $k$-colorings of $G_{R}$ and the $k$-colorings of $\hat{G}$ as follows. Let $Q$ be the set of edges from the set $\{v_{1},\ldots,v_{r}\}$ to $\{v_{r+1},\ldots,v_{n}\}$. Then w.h.p. $|Q|=O(1)$ and no vertex in $\{v_{r+1},\ldots,v_{n}\}$ is incident to more than one edge in $Q$. Furthermore, since $R$ admits a unique $k$-coloring, each edge in $Q$ forbids its endpoint in $\{v_{r+1},\ldots,v_{n}\}$ exactly one color. Hence, the edges in $Q$ impose constraints $c_{1},\ldots,c_{M}$ on $M=|Q|$ randomly chosen vertices $w_{1},\ldots,w_{M}$ as in Lemma 10. Therefore, (8) implies that

Furthermore, as we may add another $\ln n$ random edges to $\hat{G}$ without shifting the distribution by more than $o(1)$ in total variation distance, and since each of these $\ln n$ edges reduces the expected number of colorings by $k^{-1}$, Markov’s inequality entails that

A.4 Proof of Theorem 2.5

Suppose that $d\leq(1-\varepsilon)k\ln k$, and that $k\geq k_{0}(\varepsilon)$ for a sufficiently large $k_{0}(\varepsilon)$. Let $q=5$ and recall that a graph is $\zeta$-choosable if for any assignments of color lists of length at least $\zeta$ to the vertices of the graph there is a proper coloring such that each vertex receives a color from its list. To prove Theorem 2.5, we consider the property $\mathcal{E}$ that all vertices are loose and the following condition $\mathcal{D}$:

For any set $S\subset V$ of size $|S|\leq g(n)$ the subgraph induced on $S$ is $(q-1)$-choosable.

Here $q>0$ is a constant and $g(n)=\sqrt{nf(n)}=o(n)$, where $f(n)$ is the function from Theorem 0.A.1.

With high probability the random graph $G(n,m)$ satisfies $\mathcal{D}$.

Since $m=O(n)$, this follows from a standard first moment argument. ∎

By Theorem 0.A.1, we just need to establish (7). Thus, let $\sigma\in\left[{k}\right]^{n}$ be a coloring such that the color classes $V_{i}=\sigma^{-1}(i)$ satisfy $|V_{i}|\sim n/k$, and let $G$ be a random graph with $m$ edges such that $\sigma$ is a $k$-coloring of $G$. Let $v_{0}\in V$ be any vertex; without loss of generality we may assume that $\sigma(v_{0})=1$. In addition, let $1<l\leq k$ be the “target color” for $v_{0}$. If $v_{0}$ has no neighbor in $V_{l}$, then we can just assign this color to $v_{0}$.

Otherwise, we run the following process. In the course of the process, every vertex is either awake, dead, or asleep. Initially, all the neighbors of $v_{0}$ in $V_{l}$ are awake, $v$ is dead, and all other vertices are asleep. In each step of the process, pick an awake vertex $w$ arbitrarily and declare it dead (if there is no awake vertex, terminate the process). If there are at least $q$ colors $c_{1}(w),\ldots,c_{q}(w)$ such that $w$ has no neighbor in $V_{c_{i}(w)}$, then we do nothing. Otherwise, we pick $q$ colors $c_{1}(w),\ldots,c_{q}(w)$ randomly and declare all asleep neighbors of $w$ in $V_{c_{j}(w)}$ awake for $1\leq j\leq q$.

With probability at least $1-\exp(-f(n))$ there are at most $g(n)$ dead vertices when the process terminates.

We show that the aforementioned process is dominated by a branching process in which the expected number of successors is less than one. Then the assertion follows from Chernoff bounds.

To set up the analogy, note that the expected number of neighbors of any $w\in V\setminus V_{i}$ in $V_{i}$ is asymptotically $2m/k<\frac{1-\varepsilon}{1-k}\cdot\ln k$. Hence, the probability that $w$ has no neighbor in $V_{i}$ is at least $k^{\varepsilon/2-1}$. Therefore, the expected number of classes $i\not=\sigma(w)$ in which $w$ has no neighbor is at least $(k-1)k^{\varepsilon/2-1}\geq k^{\varepsilon/3}$. Furthermore, the number of such classes is asymptotically binomially distributed. Therefore, assuming that $k$ is sufficiently large, we conclude that the probability that there are less than $q$ classes in which $w$ has no neighbor is less than $k^{-1}$. Given that this is so, the number of neighbors of $w$ in each of the $q$ chosen classes $c_{1}(w),\ldots,c_{q}(w)$ has mean at most $2\ln k$. Therefore, the expected number of newly awake vertices resulting from $w$ is at most $2k^{-1}\ln k$. Thus, the above process is dominated by a branching process with successor rate $2k^{-1}\ln k<1$. Therefore, the assertion follows from stochastic domiance and Chernoff bounds. ∎