NDMI 058 -- Flows and Cycles in Graphs -- Toky a cykly v grafech

Robert Šámal

More info in SIS.

Tutte has defined nowhere-zero flows in graphs as a dual notion to colorings. It has been a fascinating area of research for the past few decades. It also includes problems about cycle double cover, covering a graph by matchings, and other related problems. For better idea what the lecture is about, see the web page of the last edition of this lecture. (In Czech though.) It is likely this year we will cover slightly different material.

Time and place

Thursday 15:40 S10 lecture
Thursday 17:10 S10 tutorials (not every week)
We start Feb 24, 2022.

Literature

My lecture notes.
Same text, with handwritten comments "whiteboard record"
C.Q.Zhang: Integer flows and cycle covers of graphs. Monographs and Textbooks in Pure and Applied Mathematics, 205. Marcel Dekker, Inc., New York, 1997.
C.Q.Zhang: Circuit double cover of graphs. London Mathematical Society Lecture Note Series, 399. Cambridge University Press, Cambridge, 2012.

Exercise

Homeworks plus discussion in class, cca once per two weeks.
  1. First set of exercises. Will be discussed on Mar 10.
  2. Second set of exercises. Will be discussed on Mar 31.

What happened in class

Lecture 1 Feb 24, 2022
Intro: what is CDC, what is a flow. Flow polynomial. Graphs with a NZ 2-flow, 3-flow, 4-flow. See the board for details.
Lecture 2 Mar 3, 2022
Nowhere zero flow -- integral and modular. Tutte's theorem about their equivalence! Flow number of a graph is the chromatic number of the dual. See the board for details.
Lecture 3 Mar 10, 2022
Proof that $k$-NZF is the same as ${\mathbb Z}_k$-NZF. 4-NZF in 4-edge-connected graph, 8-NZF in any bridgeless graph. 5-flow conjectue. Flows and tesnsions. See the board for details.
Lecture 4 Mar 17, 2022
Flows and tensions. Snarks and their constructions (in particular Isaacs' dot product). Flower snarks. See the board for details.
Lecture 5 Mar 24, 2022
Cycle double cover conjecture. Equivalent versions for small number of cycles. Minimal counterexamples. See the board for details.
Lecture 6 Mar 31, 2022
More properties of minimal counterexamples to CDC. Splitting lemma. See the board for details.
Lecture 7 Apr 7, 2022
Shortest cycle cover. Berge-Fulkerson conjecture. Matching polytope and its applications. See the board for details.
Lecture 8 Apr 14, 2022
Every bridgeless graph has a 6-flow. Properties of minimal counterexample to the 5-flow conjecture. See the board for details.
Lecture 9 Apr 21, 2022
Group connectivity. See the board for details.
Lecture 10 Apr 28, 2022
Faithful cycle covers. See the board for details.
Lecture 11 May 12, 2022
Nash-Williams theorem about disjoint spanning trees. See the board for details.