Minimal counterexamples to flow conjectures

• Thesis title in Czech: Minimální protipříklady na hypotézy o tocích
• Thesis title in English: Minimal counterexamples to flow conjectures
• Key words: nenulové toky, minimální protipříklad
• English key words: nowhere zero flows, minimal counterexample
• Academic year of topic announcement: 2013/2014
• Thesis type: diploma thesis
• Thesis language: angličtina
• Department: Computer Science Institute of Charles University (32-IUUK)
• Supervisor: doc. Mgr. Robert Šámal, Ph.D.
• Author: Mgr. Peter Korcsok - assigned and confirmed by the Study Dept.
• Date of registration: 11.03.2014
• Date of assignment: 14.03.2014
• Confirmed by Study dept. on: 21.03.2014
• Date and time of defence: 03.06.2015 09:00
• Date of electronic submission: 05.05.2015
• Date of submission of printed version: 07.05.2015
• Date of proceeded defence: 03.06.2015
• Opponents: Andrew Goodall, D.Phil.

Guidelines

As Tutte's 3-, 4- and 5-Flow conjectures [3] are open for decades, attempts to attack them are frequently framed as the study of minimal counterexample.

In recent papers Kochol [1,2] introduces an interesting idea that enables him to show that the minimal counterexample cannot contain short cycles.
The core of the procedure is in the contraction/deletion formula that is used to describe the number of flows by means of certain scalar products.
It leads to a concrete question about ranks of certain matrices; this is verified by computer.

The task of the student is to understand these two papers and to implement them (in order to verify them, as the original papers' author
doesn't share his implementation). If the implementation is sufficiently efficient, the bound on the girth of minimal counterexample
should be improved as well. Student will try to find a way to use the technique on other conjectures as well (such as
the Cycle Double Cover conjecture).

References

[1] Martin Kochol: Restrictions On Smallest Counterexamples To The 5-Flow Conjecture. Combinatorica 26, 2006, no. 1, 83–89.

[2] Martin Kochol: Smallest Counterexample to the 5-Flow Conjecture Has Girth at Least Eleven. Journal of Combinatorial Theory, Series B 100, 2010, no. 4, 381–389.

[3] Cun-Quan Zhang: Integer flows and cycle covers of graphs. Monographs and Textbooks in Pure and Applied Mathematics, 205. Marcel Dekker, Inc., New York, 1997.