Visualization of the OpenAI proof of the Cycle Double Cover conjecture

Visualization of the OpenAI proof of the Cycle Double Cover conjecture

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:

$$t_u = t_v \quad \text{and} \quad t_u + f(e) = t_v + f(e)$$

or

$$t_u = t_v + f(e) \quad \text{and} \quad t_u + f(e) = t_v$$

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:

$$t_u = t_v + s(e) \cdot f(e)$$

with $s(e)$ either $0$ (not swapped) or $1$ (swapped).

Rewrite this to:

$$t_u + t_v + s(e) \cdot f(e) = 0$$

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:

$$t_u + t_v + s(e) \cdot f(e) = d(e)$$

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$.

$$t_u + t_v + s(e) \cdot f(e) = d(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...