Algorithmic Barriers from Phase Transitions

Definition 1

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

Remark 1

The term cluster comes from physics. Requiring 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)$.

2.1 Shattering

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}\rightarrow 0$. The best rigorously analyzed poly-time k-coloring algorithm w.h. p. fails for $d\geq(1+\delta_{k})k\ln k$, where $\delta_{k}\rightarrow 0$.

Theorem 1

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

$$(1+\epsilon_{k})k\ln k\leq d\leq(2-\epsilon_{k})k\ln k. \eqno{\hbox{(1)}}$$ View Source(1+\epsilon_{k})k\ln k\leq d\leq(2-\epsilon_{k})k\ln k. \eqno{\hbox{(1)}}

• 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 rigorously analyzed poly-time satisfiability algorithm w.h.p. fails for $r>2^{k+1}/k$. In [23], non-rigorous, but mathematically sophisticated evidence is given that a different algorithm succeeds for $r=\Theta((2^{k}/k)\ln k)$ but not higher.

Theorem 2

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

$$(1+\epsilon_{k}){2^{k}\over k}\ln k\leq r\leq(1-\epsilon_{k})2^{k}\ln 2. \eqno{\hbox{(2)}}$$ View Source(1+\epsilon_{k}){2^{k}\over k}\ln k\leq r\leq(1-\epsilon_{k})2^{k}\ln 2. \eqno{\hbox{(2)}}

• 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-{3\over 2}$. The best rigorously analyzed poly-time 2-coloring algorithm w.h.p. fails for $r>2^{k}/k$. In [23], non-rigorous, but mathematically sophisticated evidence is given that a different algorithm succeeds for $r=\Theta((2^{k}/k)\ln k)$, but not higher.

Theorem 3

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

$$(1+\epsilon_{k}){2^{k-1}\over k}\ln k\leq r\leq(1-\epsilon_{k})2^{k-1}\ln 2. \eqno{\hbox{(3)}}$$ View Source(1+\epsilon_{k}){2^{k-1}\over k}\ln k\leq r\leq(1-\epsilon_{k})2^{k-1}\ln 2. \eqno{\hbox{(3)}}

2.2 Rigidity

The regions mentioned in Theorems 1, 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”.

We will prove that in a typical solution, while before the phase transition 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 {\cal S}(I)\}$. We let ${\cal U}={\cal U}_{n, m}$ be the probability distribution induced on $\Lambda_{n, m}$ by the following experiment:

Choose an instance $I\in I_{n, m}$ uniformly at random. If ${\cal S}(I)\neq\emptyset$, select $\sigma\in {\cal S}(I)$ uniformly at random.

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

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

The picture drawn by Theorem 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 general additional difficulties imposed by random k-SAT in Section 4.)

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 5, w.u.p.p. $(I, \sigma)$ is such that setting the color of any vertex to any color only requires changing the color of $O(\log n)$ other vertices.

3.1 Algorithms

Attempts for a “quick improvement” upon either of the naive algorithms mentioned in the introduction for satisfi-ability/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 [22], Mezard, 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. Later, SP was extended to other problems, e.g., k-coloring [9] and Max $k$ -SAT [8]. 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. The problem seems to lie with the “dec-imation” aspect of the algorithm, i.e., the process of repeatedly selecting (and setting permanently) the most “biased” variables in the formula (we comment on this further be-low). 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 an approximation of the cluster projections), then so can a much simpler algorithm, namely Belief Propagation (BP), i.e., dynamic programming on trees (for approximating the marginal probability distribution of the variables with respect to the uniform measure over satisfying assign-ments).

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 [23], Montanari et al. showed that (even within the relatively generous assumptions of statistical physics computations) the following Gibbs-sampling algorithm fails above density $e(2^{k}/k)$, i.e., step 2 below fails to converge after only a small fraction of all variables have been assigned a value:

1. Select a variable $v$ at random.

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

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

3.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 [19] 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 that the distribution resulting from first choosing $G=G_{n, 1/2}$ and then planting a clique of size $(1+\epsilon)\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 [19] 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 [12][13] 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, in stark contrast with the regime we analyze.

3.3 Solution-space Geometry

In [7][21] 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 [7][21] vs. those employed here. In those works, properties such as the existence of frozen variables were shown to hold for all satisfying assignments and were correspondingly 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 random solutions of random instances. 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.

5.1 The Transfer for Random Graph Coloring

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 $[k]$. We are interested in the probability distribution ${\cal 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 ${\cal P}_{n, m}$ on $\Lambda_{n, m}$ induced by following expermient.

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

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

3. Output the pair $(G, \sigma)$.

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

Theorem 6

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 ${\cal D}$ be any graph property such that $G(n, m)$ has ${\cal D}$ with probability $1-o(1)$, and let ${\cal E}$ be any property of pairs $(G, \sigma)\in\Lambda_{n, m}$. If for all sufficiently large $n$,

$${\Pr}_{P_{nm}}[(G, \sigma)\ { has}\ {\cal E}\vert G\ { has}\ {\cal D}]\geq 1-\exp(-f(n)), \eqno{\hbox{(5)}}$$ View Source{\Pr}_{P_{nm}}[(G, \sigma)\ { has}\ {\cal E}\vert G\ { has}\ {\cal D}]\geq 1-\exp(-f(n)), \eqno{\hbox{(5)}}

then $\Pr_{{\cal U}_{n, m}}[(G, \sigma)$ has ${\cal E}]=1-o(1)$.

5.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 assignment 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 5, we consider the property ${\cal E}$ that all vertices are $o(n)$ -loose and the following condition ${\cal D}$:

For any set $S\subset V$ of size $\vert S\vert \leq g(n)$ the subgraph induced on $S$ is 3-choosable. Here $g(n)$ is some function such that $f(n)\ll g(n)=o(n)$, where $f(n)$ is the function from Theorem 6. A standard argument shows that a random graph $G(n, m)$ with $m= O(n)$ satisfies ${\cal D}$ w.h.p.

By Theorem 6, we are thus left to establish (5). Let $\sigma\in[k]^{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 $\vert V_{i}\vert \sim n/k$. Let $v_{0}\in V$ be any vertex, and let $l\neq\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 dist $(\sigma, \tau)\leq g(n)$.

If $v_{0}$ has no neighbor in $V_{1}$, then we can just assign color $l$ 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_{0}$ 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, the process terminates). If there are at least four colors $c_{1}(w), \ldots, c_{4}(w)$ available such that $w$ has no asleep neighbor in $V_{c_{i}(w)}$, then we do nothing. Otherwise, we pick four colors $c_{1}(w), \ldots, c_{4}(w)$ randomly and declare all asleep neighbors of $w$ in $V_{c_{j}(w)}$ awake for $1\leq j\leq 4$.

Proof sketch. We relate the above process to a subcritical branching process. To this end, we bound the expected “off-spring” (i.e., number of new awake vertices) generated in any step of the process. Suppose that in some step of the process an awake vertex $w$ is chosen. To bound the expected offspring, we basically observe that when $d<(1-\varepsilon)k\ln k$ it is very likely that a vertex $w$ has four immediately available colors, and thus no offspring will be generated at all. More precisely, the number of neighbors of $w$ in any class $V_{i}$ with $i\neq\sigma(w)$ is asymptotically Poisson with mean

View Source{2m\over (k-1)n}\leq(1-\varepsilon){k\ln k\over k-1}.

Hence, the probability that $w$ does not have a neighbor in $V_{i}$ is asymptotically equal to

View Source\pi_{k}=\exp\left(-{2m\over (k-1)n}\right)\geq k^{\varepsilon/2-1}

(for sufficiently large $k$). As there are $k$ colors in total, the expected number of colors $i\neq\sigma(w)$ such that $w$ has no neighbor in $V_{i}$ is asymptotically Poisson with mean $(k- 1)\pi_{k}\geq k^{\varepsilon/3}$. Consequently, the probability that $w$ has at least than four available colors is at least

View Source1-\Pr\Big[{\rm Poisson}(k^{\varepsilon/3}) < 4\Big]\geq 1-\exp(-k^{\varepsilon/4}), \eqno{\hbox{(6)}}

and in this case $w$ does not produce any offspring at all. If $w$ has fewer than four available colors, then the number of neighbors of $w$ in a randomly chosen color class is stochastically dominated by a Poisson distribution with mean $k\ln k$ conditioned on being at least one. Hence, in this case we can bound the expected number of newly awake vertices by $4\cdot 2k\ln k$. Thus, (6) entails that the expected number of offspring vertices is at most $8k\ln k\cdot\exp(-k^{\varepsilon/4})<1$.

As a consequence, the total number of dead vertices at the end of the process is dominated by the total number of offspring generated by a branching process with rate at most $8k\ln k\cdot\exp(-k^{\varepsilon/4})<1$. Therefore, standard tail bounds for branching processes imply the assertion. $\square$

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\backslash D$. Moreover, conditioning on the event ${\cal D}$, we can assign color $l$ to $v_{0}$ and a color from the list $\{c_{1}(w), \ldots, c_{5}(w)\}\backslash \{l\}$ to each $w\in D\backslash \{v_{0}\}$. Thus, the new coloring $\tau$ differs from $\sigma$ on at most $\vert D\vert \leq g(n)= o(n)$ vertices.

5.3 Rigid Variables Above the Transition

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

View Source\eqalignno{&{\rm There\ is\ a\ subgraph}\ G_{\ast}\subset\ G\ {\rm of\ size}\ \vert V(G_{\ast})\vert \geq \cr &(1\ -\alpha)n\ {\rm such\ that\ for\ every\ vertex}\ v\ {\rm of}\ G_{\ast}\ {\rm and}\cr &{\rm each\ color}\ i\neq\sigma(v)\ {\rm there\ are\ at\ least}\ \beta\ln k\ {\rm vertices}&\hbox{(7)}\cr &w\ {\rm in}\ G_{\ast}\ {\rm that\ are\ adjacent\ \to}\ v\ {\rm such\ that}\ \sigma(w)=i.}

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

Proof sketch. Let $(G, \sigma)\in\Lambda_{n, m}$ be a random pair chosen from the distribution ${\cal P}_{n, m}$. We may assume that $\vert \sigma^{-1}(i)\vert \sim n/k$ for all $i$. To obtain the graph $G_{\ast}$, 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 some fixed $\delta>0$, because for each vertex $w$ the expected number of neighbors in another color class is asymptotically Poisson with mean at least $(1+\varepsilon)\ln k$. Then, we keep removing vertices from $H$ that have “a lot” of neighbors outside of $H$. Given the event ${\cal D}$, we can show that with probabiltiy $1-\exp(-\Omega(n))$ the final result of this process is a subgraph $G_{\ast}$ that satisfies (7). $\square$

Furthermore, the following lemma follows from a standard “first moment” argument.

Lemma 3

W.h.p. the random graph $G=G_{n, m}$ _. has thetol-

$$\eqalignno{&{ There\ is\ no\ set}\ S\ { of\ vertices\ of\ size}\ \vert S\vert \leq n/(k\ln k)\cr &{ such\ that}\ S\ { spans\ at\ least}\ {1\over 2}\vert S\vert \beta\ln k\ { edges}. &\hbox{(8)}}$$ View Source\eqalignno{&{ There\ is\ no\ set}\ S\ { of\ vertices\ of\ size}\ \vert S\vert \leq n/(k\ln k)\cr &{ such\ that}\ S\ { spans\ at\ least}\ {1\over 2}\vert S\vert \beta\ln k\ { edges}. &\hbox{(8)}}

To complete the proof of Theorem 4 for coloring, consider a pair $(G, \sigma)$ chosen from ${\cal U}_{n, m}$. By Lemma 2 and

Theorem 6 there is a subgraph $G_{\ast}$ as in (7) w.h’ p ‘Moreover, by Lemma 3 we may assume that $G$ satisfies (8). Now, assume for contradiction that $G$ has a k-coloring $\tau\neq\sigma$ such that the set $U=\{v\in G_{\ast}:\sigma(v)\neq\tau(v)\}$ has size $\vert U\vert \leq n/(k\ln k)$. Let

View Source\eqalignno{&U_{i}^{+} = \{v\in G_{\ast}:\tau(v)=i\neq\sigma(v)\},\cr &U_{i}^{-} = \{v\in G_{\ast}:\sigma(v)=i\neq\tau(v)\}}

for $1\leq i\leq k$. Then

View Source\vert U\vert =\displaystyle\sum_{i=1}^{k}\vert U_{i}^{+}\vert =\sum_{i=1}^{k}\vert U_{i}^{-}\vert. \eqno{\hbox{(9)}}

Every vertex $v\in G_{\ast}\backslash \sigma^{-1}(i)$ has at least $\beta\ln k$ neighbors in $G_{\ast}\cap\sigma^{-1}(i)$. Hence, if $v\in U_{i}^{+}$, then all of these neighbors lie inside of $U_{i}^{-}$. We claim that this implies that $\vert U_{i}^{+}\vert <\vert U_{i}^{-}\vert$; for assume that $U_{i}^{+}\geq U_{i}^{-}$. Set $S=U_{i}^{+}\cup U_{i}^{-}$. Then $\vert S\vert \leq\vert U\vert \leq n/(k\ln k)$, and $S$ spans at least $\vert S\vert {\beta\over 2}\ln k$ edges, in contradiction to (8). Thus, we conclude that $\vert U_{i}^{+}\vert <\vert U_{i}^{-}\vert$ for all $i$, in contradiction to (9). Hence, all the vertices in $G_{\ast}$ are ${n\over k\ln k}$ -rigid.

5.4 Proof of Theorem 1

Theorem 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_{\sigma,\tau}^{ij})_{1\leq i, j\leq k}$ be the matrix with entries

View SourceM_{\sigma,\tau}^{ij}=n^{-1}\vert \sigma^{-1}(i)\cap\tau^{-1}(j)\vert.

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

View Sourcef_{\sigma}(\tau)=\Vert M_{\sigma,\tau}\Vert_{F}^{2}=\displaystyle\sum_{i, j=1}^{k}(M_{\sigma,\tau}^{ij}) ^{2}\,

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 $[k]^{n}$ of k-partitions to the interval $[k^{-2}, f_{\sigma}(\sigma)]$, where $f_{\sigma}(\sigma)\geq k^{-1}$. Thus, the larger $f_{\sigma}(\tau)$, the more $\tau$ resembles $\sigma$. Furthermore, for a fixed $\sigma\in {\cal S}(G)$ and a number $\lambda>0$ we let

View Sourceg_{\sigma, G,\lambda}(x)=\vert \{\tau\in[k]^{n}:f_{\sigma}(\tau)=x\wedge H(\tau)\leq\lambda n\}\vert.

lowing property.

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

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

Finally, by Theorem 6, to prove Lemma 4 it is sufficient to show the following.

The proof of Lemma 5 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[k]^{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 [4] 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 5 follows from Markov's inequality.