Introduction

To introduce the subject of the paper we begin with the illustrative example of \(k\)-coloring a random graph.

The random \(k\)-coloring problem is defined as follows:

Let \(G\) be a random graph with average degree \(d\). Is it possible to properly \(k\)-color the vertices of \(G\)?

The answer to this existential problem is, that there is a threshold at \(d=2k\ln k\).

while not all vertices are colored:
  Let v be a vertex with the fewest remaining choices for its color
  Assign v a random available color

Let the algorithmic threshold denote the largest edge density where we have efficient algorithms for \(k\)-coloring. Let the existence threshold denote the largest edge density where we are guaranteed (with good probability) that a \(k\)-coloring exists. Note that there is a gap between the algorithmic threshold and the existence threshold. This is a quite general phenomenon across many CSPs; for instance it also occurs for \(k\)-SAT. Achiloptas and Coja-Oghlan’s goal in this paper is to provide an explanation of the gap between these thresholds. They do so by giving a description of the solution space geometry, and showing that this space undergoes a dramatic change when we cross the threshold below which we have efficient algorithms for \(k\)-coloring.

First we define what we mean by solution space geometry, and describe qualitatively the phase transition that occurs. The space of \(k\)-colorings is simply \([k]^{n}\). We can think of this as a “landscape”. The height in the landscape corresponds to the number of violated constraints (i.e., monochromatic edges). The height of a path between two colorings is the largest height at any coloring along the path. The distance between two colorings is the number of vertices that they assign different colors. Below the algorithmic threshold they show that there is a “giant ball” of solutions: this ball is large, and it is easy to move between solutions, in the sense that starting from a given solution there is a nearby solution that you can walk to along a low height path. In contrast, above the algorithmic threshold (but still below the existence threshold so that solutions exist) the solution space shatters and looks like an “error correcting code”. More specifically, the solution space transitions to consisting of an exponential number of regions, none of which are very large, and such that the regions are very far apart and separated by large heights (or “energy barriers”).

The most important idea in their analysis is a transfer principle. Roughly speaking this principle says that the view of the landscape from a random valley is basically the same as the view from a planted valley. In a planted instance of random \(k\)-coloring instead of uniformly randomly choosing a graph \(G\) of appropriate average degree, we first fix a coloring \(\sigma\in [k]^{n}\) and then select \(G\) from amongst graphs with the appropriate average degree which are properly colored by \(\sigma\). Intuitively, if a random coloring instance has a very large number of solutions on average then adding one more solution won’t change its landscape too much. However, reasoning about the planted model turns out to be much easier than reasoning about the uniform model.

Now we develop these notions more formally. For graph \(G\) and coloring \(\sigma\in [k]^{n}\) let \(H_G(\sigma)\) count the number of violated constraints (monochromatic edges) if we color \(G\) via \(\sigma\). Let \(S(G)\) denote the set of colorings \(\sigma\) with height \(H_G(\sigma) = 0\); that is, \(S(G)\) is the set of proper \(k\)-colorings of \(G\). Define the distance between two colorings to be the number of vertices which they assign different colors. A cluster of \(G\) is a connected component of \(S(G)\), where two colorings are considered adjacent if they have distance \(1\) (differ on a single vertex). A region is a non-empty union of clusters.

Fix graph \(G\) and a proper \(k\)-coloring \(\sigma\) of \(G\). We say that a vertex \(v\) is \(f(n)\)-rigid (with respect to \(G,\sigma\)) if every coloring \(\tau\in S(G)\setminus \left\{ \sigma\right\}\) is distance at least \(f(n)\) away from \(\sigma\). Otherwise we say that vertex \(v\) is \(f(n)\)-loose. They show:

proof sketches

Now we present proof sketches for these theorems.

The most important part of the argument is the transfer principle, i.e., showing that we can understand the view from a random solution by looking at the view from a planted solution.

To state the transfer principle we must first formally define the distributions we are concerned with. First, define the uniform model \(U_{n,m}\) as follows:

Sample a random graph \(G\) with \(m\) edges, and then sample a random proper \(k\)-coloring \(\chi\) of \(G\) (assuming that one exists). Output \((G, \chi)\).

Now, define the planted model \(P_{n,m}\) as follows:

Generate a uniformly random \(k\)-partition \(\chi\in [k]^n\). Choose a uniformly random subset of \(m\) edges from amongst the edges that are not monochromatic under \(\chi\). Output \((G, \chi)\).

In the remainder of the note we will show how to use the transfer principle to prove their results about loose/rigid variables and about shattering/non-shattering.

Loose Variables Below the Algorithm Threshold

In this section we show that below the algorithm threshold with good probability all variables are loose. Recall what this means: for any proper coloring \(\chi\) of our graph and any vertex \(i\in [n]\) we want to exhibit a “nearby” coloring \(\tau\) – nearby in the sense that we want \(\tau,\chi\) to assign different colors to at most \(o(n)\) vertices – with \(\tau(i)\neq \chi(i)\). To show this we give a simple algorithm that give \(\chi,i\) finds such a nearby coloring where \(i\)’s color is flipped.

The analysis of the algorithm will use notion of list chromatic number. We say that graph \(G\) is \(\eta\)-list-colorable if for any set of color lists \(C_1,\ldots, C_n \in \binom{[k]}{\eta}\) there exists a proper coloring \(\chi_1,\ldots, \chi_n\) of the vertices with \(\chi_i \in C_i\) for all \(i\). We remark that the list-chromatic number of a graph (the smallest \(\eta\) for which \(G\) is \(\eta\)-list-colorable) is at least as large, and possibly larger, than the chromatic number of \(G\).

Now we define the properties \(D,E\) which we will use in the transfer principle.

Let \(E\) be the property of \((G,\chi)\) that all vertices are \(o(n)\)-loose.

Let \(D\) be the property of \(G\) that for any set \(S\subseteq V\) of size at most \(o(n)\) \(S\) is \(4\)-list-colorable.

Proof. We give an algorithm for finding a nearby solution. Throughout the algorithm vertices will be either asleep, awake, or dead. Start with all vertices asleep. Let \(v_0\) be the vertex we want to change the color of and let \(V_1,\ldots, V_k\) be the color classes. Let \(V_\ell\) be the target color that we want to switch \(v_0\) to be. To start we kill vertex \(v_0\). If \(v_0\) has no neighbors in \(V_\ell\) then it is trivial. Otherwise we wake up \(v_0\)’s neighbors in \(V_{\ell}\). While there are awake vertices remaining we then repeat the following process:

• Pick a random awake vertex \(w\) and kill it.
• If there are at least \(5\) color classes that \(w\) has no edges to, then we do nothing more.
• Else, choose \(5\) color classes randomly and wake up all of \(w\)’s neighbors in these color classes.

It turns out that this is a subcritical branching process. So the number of dead vertices is at most \(o(n)\).

Now we describe how to color vertices. If a vertex is still asleep at the end we assign it its original color. For the dead vertices besides \(v_0\) we give them each a list of at least \(4\) colors, namely the \(5\) sets that they had no neighbors in if applicable, or the \(5\) sets that they woke up, except we don’t let them choose \(V_\ell\).

Then we use the \(4\)-list-colorable property to get a coloring for the induced subgraph on dead vertices. Finally we give vertex \(v_0\) the color \(\ell\).

We claim that this is a proper coloring. Edges between dead vertices are ok by assumption that the subgraph was list-colorable so we could chose a coloring. Edges between asleep vertices are ok because they were ok to start with and we didn’t change them. Edges between asleep and dead vertices are ok because if there is an edge between asleep vertex \(u\) and dead vertex \(w\) then \(w\) did not get labelled with the color of \(u\) or \(u\) would have been woken up.

Rigid variables above the algorithm threshold

shattering

Now we will prove shattering. They want some notion of distance that plays nicely with permuting colors, not exactly sure why but whatever.

Define \(M_{\sigma,\tau}^{ij} = \frac{1}{n} |\sigma^{-1}(i)\cap \tau^{-1}(j)|\). Our notion of distance between \(\sigma, \tau\) is now gonna be frobenius norm of \(M_{\sigma, \tau}\). Checking for \(\sigma = \tau\) it is much bigger than if \(\sigma,\tau\) are “uncorrelated”.

It is clear how this allows us to define regions.

ok so to prove the theorem

step 1: transfer principle ofc.

gg