Fakulta matematiky, fyziky
a informatiky
Univerzita Komenského v Bratislave

Seminár z teórie grafov - Lukáš Gáborik (10.10.2024)

vo štvrtok 10.10.2024 o 9:50 hod. v miestnosti M 213


07. 10. 2024 15.31 hod.
Od: Martin Škoviera

Prednášajúci: Lukáš Gáborík 

Názov: Chebyshev and Manhattan nowhere-zero flows

Termín: 10.10.2024, 9:50 hod., M 213


Abstrakt:
The area of nowhere-zero flows has been widely researched since its introduction by Tutte in 1954, when he also conjectured that each bridgeless graph has a nowhere-zero 5-flow. Recently, Mattiolo et al. researched real-valued nowhere-zero flows in two dimensions. They found some interesting properties (as rationality), in which 1D and 2D flows differ. We examine whether one can achieve better consistency by changing the considered norm from the Euclidean to the Chebyshev or the Manhattan one. In the two-dimensional case, we prove a one-to-one correspondence between Chebyshev and Manhattan flows, characterise graphs with unit vector flows and find some bounds on the flow number. Moreover, we observe a structure whose existence implies a 1D 5-flow and a 2D 2.5-flow, which opens a new possible way to prove Tutte's 5-flow conjecture. This is joint work with Sascha Kurz, Giuseppe Mazzuoccolo, Jozef Rajník, Florian Rieg and Gloria Tabarelli.

Stránka seminára