Two days ago, OpenAI made available a proof of Cycle Double Cover conjecture: Every cubic graph without a bridge has a set of cycles that contains each edge exactly twice.
This post visualizes parts of the proof.
They start from a nowhere-zero $\mathbb{Z}_2^3$-flow $f$ that's known to exist in these graphs and turn it into 8 unions of cycles that contain each edge exactly twice.
A nowhere-zero $\mathbb{Z}_2^3$-flow is an assignment of a number from 001, 010, 011, 100, 101, 110, 111 to each edge so that the sum at each vertex is 000. Here, $+$ is XOR because it's bitwise addition without carry.
We just have to say which two cycles each edge belongs to and then check the local condition that every vertex is adjacent to 0 or 2 edges of each cycle. Then that automatically makes it a union of cycles. There will be 8 unions of cycles, one labelled by each of 000, 001, 010, 011, 100, 101, 110, 111.
Assigning cycles #
We obviously want to somehow pick cycle membership depending on the $\mathbb{Z}_2^3$-flow.
For each vertex, we'll pick a $t_v \in \mathbb{Z}_2^3$ to be determined later. That vertex will then "say" which cycles each of its edges belong to.
This is a description of the construction, and we'll then see why it works.
- For one edge $e_1$ around $v$, we'll put it in cycles $t$ and $t + f(e_1)$.
- For another edge $e_2$ around $v$, we'll put it in cycles $t$ and $t + f(e_2)$.
- For the third edge, we have no choice. It has to be in cycle numbers $t + f(e_1)$ and $t + f(e_2)$, so we'll put it there.
How do we choose which edge is the "third edge" at each vertex? Arbitrarily. We can always make it work in the end. But $t_v$ for each $v$ needs to be chosen carefully.
Agreement #
Now we did something strange. We're supposed to say which cycle each edge belongs to, but now each vertex has a say. And the two ends of an edge may not agree.
When do they agree? It seems like we have special cases depending on whether one side or the other is a third edge. So let's look at the case where $e$ is not the third edge of either end. We'll see that in the end, having third edges just adds a constant depending only on $f$.
In that case, to get agreement, we need:
or
Since $f(e) + f(e) = 0$, the two conditions are redundant and we only need one. Also, whether a swap is needed can be encoded uniformly as:
with $s(e)$ either $0$ (not swapped) or $1$ (swapped). Rewrite this to:
Let's make our task harder: on top of $t$, we also have to provide the correct value for $s$.
Now we focus on finding $t$ and $s$ so that every equation for every edge is satisfied.
Third edges #
If $e$ is the third edge of one or both its ends, the equation will become: and we think of $d(e)$ as a constant that depends only on the flow $f$ and edge $e$.
I suggest skipping this part for now and coming back to it later when needed.
For a third edge, the difference between the two cycle numbers of $e$ is $(t + f(e_2)) - (t - f(e_3)) = t + f(e_2) + t + f(e_3) = f(e_2) + f(e_3) = f(e_1)$ since $f$ is a flow and $f(e_1) + f(e_2) + f(e_3) = 0$. So adding $f(e_1)$ still swaps the two cycle numbers. When $e$ is the third edge of $u$, an extra $f(uu_1)$ term is added (to the left-hand side, but sides don't matter mod 2) where $uu_1$ is the first edge of $u$.
When $e$ is the third edge of $v$, an extra $f(vv_1)$ term is added where $vv_1$ is the first edge of $v$.
We can just group both these terms (including whether they're non-zero) into one term $d(e)$, which only depends on the flow $f$, the selection of third edges (which is now fixed), and $e$.
System of equations #
We can write this in matrix form $M\mathbf{x} = \mathbf{d}$. $s$ and $t$ are variables, everything else is constant.
To find a solution $t$ and $s$, we'll just use something like row reduction. The only way to get stuck is if we end up with a row with all 0 on the left and a 1 in the $d$ column.
Since everything is mod 2, row operations just amounts to picking a subset of the rows and adding them together.
So suppose we have a "dependent set", rows that sum to 0 in the matrix. We just need to show summing the corresponding $d$ entries is also 0 (and not 1).
Let's represent this dependent set by a vector $r$ that's 1 for a row in the set and 0 otherwise.
What do we know about $r$?
Because the dependent rows sum to 0, the part of dependent rows for $t$ variables sum to 0. So $r$ itself is a flow (but not nowhere-zero).
The part of dependent rows for $s$ variables sum to 0 so the dot product of $f$ and $r$ is 0.
Third edges again #
Let's unpack and sum these $d$ values. Now we need to look at what $d(e)$ is and not just treat it as a constant. Here's a reminder.
$d(e)$ is the sum of two potential contributions from each end, contributing the flow $f$ of one of the other edges out of that end (or 0).
Let's write $g(u, e)$ for this potential contribution from $u$'s side to $d(e)$. For $e=uv$,
where $g(u, e) = f(e_1)$ or 0 where $e_1$ is another edge next to $u$.
So the dot product $r \cdot d = \sum_e r(e) \cdot d(e) = \sum_e r(e) \cdot g(u,e) + r(e) \cdot g(v,e)$.
That is, we need to add up $r \cdot g$ over all "half edges". We can instead sum these half edges by summing over vertices first.
Inner sum
Let's try to get a better hold of $\sum_{e: v \in e} r \cdot g(v,e)$ for an arbitrary $v$. There's exactly one third edge around $v$ and $g(v,e) = 0$ for the other two edges! For that particular third edge $e_3$, $r(e_3) \cdot g(v,e_3) = r(e_3) \cdot f(e_1)$ for some other edge $e_1$ around $v$.
For the three edges $e_1$, $e_2$, $e_3$ around $v$, let's look at the value of **all** dot products of $r$ and $f$, not just the one we need.
Since both are flows, sum of $f$ and sum of $r$ are all 0. So by distributing, the sum of each row and each column is 0. And in mod 2, $x + y + 0 = 0$ means $x = y$. So all non-diagonal values are equal!
Call this value $\lambda$, which is also the value of the dot product we are interested in: $r(e_3) \cdot f(e_1)$.
Two seemingly very different things are equal mod 2
Look at both cases.
All values equal 1: All three $r(e_1)$, $r(e_2)$, $r(e_3)$ are non-zero since all zero would mean a zero dot product for all $f$. So an odd number of non-zero $r$'s. Same parity as $\lambda$.
All values equal 0:
All the $r$ vectors are orthogonal to all the $f$ vectors because the dot product is 0 everywhere. Since $f$ is nowhere-zero, no two of $f(e_1)$, $f(e_2)$, $f(e_3)$ are equal (otherwise the third is zero). So $f$'s span a dimension 2 subspace and since there are 3 dimensions total, $r$'s span a dimension 1 subspace or less. Which only contains $000$ and possibly one other element.
So either all $r$ are $000$ or exactly one $r$ is $000$ because $r(e_1) + r(e_2) + r(e_3) = 000$. In all cases, an even number of non-zero $r$'s. Again, same parity as $\lambda$.
Therefore $\lambda$ is always the parity of the number of non-zero vectors among $r(e_1)$, $r(e_2)$, $r(e_3)$.
So $\sum_{e: v \in e} r(e) \cdot g(v,e) = \text{parity of # of non-zero } r\text{'s around } v$
Outer sum
Let's look back at the entire sum.
Let's turn "parity of # of non-zero $r$'s around $v$" into a sum. For each edge $e$ around $v$, we'll add $1$ if $e$ is non-zero and $0$ otherwise.
Convert that bool to an int or write the characteristic function to do things properly.
Now let's flip this half-edge sum again by summing over edges instead of vertices.
because $2 = 0$ mod 2.
Naming differences #
| OpenAI proof | This post |
|---|---|
| $\varepsilon$ | $s$ |
| $\eta$ | $r$ |
| $b$ (of $a,b,c$) | third edge |
| $\mathbb{F}_2^3$ | $\mathbb{Z}_2^3$ |