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

Seminár z teórie grafov - Robert Šámal (30.11.2017)

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


28. 11. 2017 13.37 hod.
Od: Martin Škoviera

Prednášajúci: Robert Šámal (Univerzita Karlova, Praha)

Názov: 3-Flows with Large Support

Termín: 30.11.2017, 9:50 hod., M/213


Abstrakt:
We prove that every 3-edge-connected graph has a 3-flow that takes on a zero value on at most one sixth of the edges. The graph $K_4$ demonstrates that this $1/6$ ratio is best possible; there is an infinite family where $1/6$ is tight. The proof involves interesting work with connectivity of the graph (relaxing to subdivisions of 2-edge-connected graphs and then reducing to cyclically 4-edge-connected ones). Joint work with M. DeVos, J. McDonald, I. Pivotto, and E. Rollova.