The regular seminar time is Wednesday, 3:35 - 4:25 p.m. The seminar takes place in person in Stevenson Center 1313. The seminar coordinator this semester is Mark Ellingham, mark.ellingham at vanderbilt.edu . Some seminars may be at unusual times, or in different rooms, or may be given as Zoom talks.
A topological perspective on the Cycle Double Cover Theorem – Mark Ellingham (Vanderbilt University)
The Cycle Double Cover Conjecture (CDCC) stated that every 2-edge-connected graph has a collection of cycles that cover every edge exactly twice. Although it was not presented in this way, the recent proof of the CDCC by OpenAI can be regarded as a topological proof, using the flow/coloring duality established by Tutte in two papers in 1946 and 1954. From this perspective, the proof goes as follows.
* As is well known, it suffices to consider 2-connected cubic graphs.
* If A = GF(2)3, then Jaeger's nowhere-zero 8-flow theorem
and a result of Tutte show that a 2-connected graph has a nowhere-zero
A-flow.
* The main part of the OpenAI proof shows that if G is a connected
cubic graph with a nowhere-zero A-flow f, then G has a
surface embedding Φ in which f is the boundary (in the homology
sense) of an A-face-coloring c. Because f is nowhere-zero,
c is a proper coloring. Since Φ has a proper face-coloring, its faces
must be bounded by cycles, which form a cycle double cover.
We explain how the OpenAI proof can be interpreted in this way, connect it to some results of Tutte, and discuss some related questions regarding flows, boundaries, and colorings in embeddings of cubic graphs.
Mark Ellingham / mark.ellingham at vanderbilt.edu