In the last lecture, we reduced the problem of cheating in (the k-times repeated m-cycle game) to finding a small set of edges in whose removal eliminates all topologically non-trivial cycles. Such a set is called a spine. To get some intuition about how many edges such a spine should contain, let’s instead look at a continuous variant of the problem.
Spines, Foams, and Isoperimetry
Consider again the -dimensional torus , which one can think of as with opposite sides identified. Say that a nice set (e.g. a compact, surface) is a spine if it intersects every non-contractible loop in . This is the continuous analog of a spine in . We will try to find such a spine with surface area, i.e. , as small as possible.
Let’s consider some easy bounds. First, it is clear that the set
is a spine with . (A moment’s thought shows that this is “equivalent” to the provers playing independent games in each coordinate of .)
To get a good lower bound, it helps to relate spines to foams which tile according to , as follows. Take two potential spines.
To determine which curve is actually a spine, we can repeatedly tile them side-by-side.
The first tiling contains the blue bi-infinite curve, which obviously gives a non-trivial cycle in , while the second yields a tiling of by bodies of volume 1. It is easy to deduce the following claim.
Claim: A surface is a spine if and only if it induces a tiling of the plane by bodies of volume 1 which is invariant under shifts by .
By the isoperimetric inequality in , this immediately yields the bound
where is the unit -dimensional sphere.
So the the surface area of an optimal spine lies somewhere between and . On the one hand, cubes tile very nicely but have large surface area. On the other hand, we have sphere-like objects which have small surface area, but don’t seem (at least intuitively) to tile very well at all. As first evidence that this isn’t quite right, note that it is known how to cover by disjoint bodies of volume at most 1 so that the surface area/volume ratio grows like . See Lemma 3.16 in this paper, which is based on Chekuri, et. al. It’s just that these covers are not invariant under shifts.
Before we reveal the answer, let’s see what consequences the corresponding discrete bounds would have for parallel repetition of the m-cycle game. If the “cube bound” were tight, we would have , which doesn’t rule out a strong parallel repetition theorem ( in the previous lecture). If the “sphere bound” were tight, we would have , which shows that . In the latter case, the approach to proving equivalence of the UGC and MAX-CUT conjectures doesn’t even get off the ground.
As the astute reader might have guessed, recently Ran Raz proved that for some constant , showing that a strong parallel repetition theorem—even for unique games—is impossible. Subsequently, Kindler, O’Donnell, Rao, and Wigderson showed that there exists a spine with . While it is not difficult to show that the continuous result implies Raz’s discrete result, we will take a direct approach found recently by Alon and Klartag.
Spectral partitioning, Cheeger’s inequality, and Dirichlet boundary conditions
First, we will show that it suffices to find a subset so that the induced graph on contains no non-trivial cycles, and is small, where we use to denote the set of edges from to in . A variant of this reduction appears in KORW. For a subset , let .
Random Partitioning Lemma: For any subset which contains no non-trivial cycles, there exists a spine with .
Let be i.i.d. uniformly random vectors, and put , with addition done over . Clearly (with probability 1), we have for some finite time . Let us define , so that is a partition into disjoint sets. Since each is isomorphic to , and , no set contains a non-trivial cycle. So if we define , then we certainly get a spine.
To calculate , we will use a “charging” argument common to many random clustering analyses. If , then we put . Clearly we can write , so it suffices to estimate for a fixed .
To this end, note that after conditioning on , is a uniformly random vertex of , and thus
By linearity of expectation, it follows that .
So our task is reduced to finding a subset with small and which contains no non-trivial cycles. A natural method for finding such a set would be to prove a bound on the smallest non-zero eigenvalue of the Laplacian on , and then use Cheeger’s inequality to conclude the existence of a good cut. But here we have to handle the special condition that should contain no non-trivial cycles.
There is a very natural way to ensure this: If we impose that our eigenfunction vanishes on the boundary of (of course any other fundamental domain would do), then the standard “sweep” algorithm which chooses a level set of the eigenfunction will always find a set that doesn’t wrap around (and therefore doesn’t contain any non-trivial cycles). The orange lines are examples of possible level sets.
Dirichlet boundary conditions for the Laplacian.
Fix a graph with . We define its combinatorial Laplacian as the matrix , where is the diagonal degree matrix with , and is the adjacency matrix of . Given a subset , we can consider the first Dirichlet eigenvalue with boundary conditions on :
By standard variational principles, there always exists a non-negative vector with for and for . If we take , then this is the lowest-energy norm-1 function on , subject to the boundary conditions.
Next, we need a version of Cheeger’s inequality for . As usual, we won’t actually need an eigenvector—any vector that has small Rayleigh quotient will do.
Discrete Cheeger inequality: If for all , then
where is the maximum degree in .
For the proof, I’ll refer to Theorem 4 in Alon-Klartag. Note that the proof for the Dirichlet version is even simpler than for the “standard” (Neumann) eigenvalues—it’s just a straightforward combination of Cauchy-Schwarz and the coarea formula.
Choosing a good eigenvector.
So to finish cheating at the odd-cycle game, we need only produce a low-energy vector on . We are aided greatly by the fact that this graph is a product of m-cycles, and thus we will only need to know about eigenvectors on the m-cycle .
Let be the adjacency matrix of the m-cycle, and let be the matrix obtained from it by replacing the last row and column by the zero vector (thus is the adjacency matrix of the -path, with an isolated vertex). Now, the adjacency matrix of is simply , where denotes the k-fold tensor product of a matrix with itself. Note that if satisfies , then
It’s easy to see that the vector with is an eigenvector of with eigenvalue and . Therefore is an eigenvector of with eigenvalue . Using (1), this implies that
Finally, using the fact that the Laplacian of is , we see that
Applying the Discrete Cheeger Inequality above, with implies that there exists a , with
Since , contains no non-trivial cycles. Applying the Random Partitioning Lemma, and noting that the number of edges in is , we conclude that there exists a spine which cuts at most a
fraction of edges.
As discussed above, this finishes the proof that is the best possible exponent in the parallel repetition theorem (even for unique games), and thus this kind of gap amplification fails to mount an attack on the Unique Games Conjecture. In the next lecture, we’ll see a more benevolent use of eigenvectors.