Minimal counterexamples to flow conjectures
| Název práce v češtině: | Minimální protipříklady na hypotézy o tocích |
|---|---|
| Název v anglickém jazyce: | Minimal counterexamples to flow conjectures |
| Klíčová slova: | nenulové toky, minimální protipříklad |
| Klíčová slova anglicky: | nowhere zero flows, minimal counterexample |
| Akademický rok vypsání: | 2013/2014 |
| Typ práce: | diplomová práce |
| Jazyk práce: | angličtina |
| Ústav: | Informatický ústav Univerzity Karlovy (32-IUUK) |
| Vedoucí / školitel: | doc. Mgr. Robert Šámal, Ph.D. |
| Řešitel: | Mgr. Peter Korcsok - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 11.03.2014 |
| Datum zadání: | 14.03.2014 |
| Datum potvrzení stud. oddělením: | 21.03.2014 |
| Datum a čas obhajoby: | 03.06.2015 09:00 |
| Datum odevzdání elektronické podoby: | 05.05.2015 |
| Datum odevzdání tištěné podoby: | 07.05.2015 |
| Datum proběhlé obhajoby: | 03.06.2015 |
| Oponenti: | Andrew Goodall, D.Phil. |
| Zásady pro vypracování |
| 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). |
| Seznam odborné literatury |
| [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. |