BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260408T090228Z
UID:Seminar-dept-1315@lxserverA.csc.liv.ac.uk.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20260224T130000
DTEND:20260224T140000
SUMMARY:School Seminar Series
DESCRIPTION:Matthias Kaul: An Invitation to Coarse Graph Theory\n\nCoarse Graph Theory concerns itself with the geometries obtained from graphs by "zooming out" slightly, i.e. by loosing the ability to distinguish vertices which are at distance less than some parameter d to each other. The first principled study of such geometries was initiated by Mikhael Gromov in the context of geometric group theory. \n\nRecently however there has been renewed attention on these objects from the viewpoint of structural graph theory, trying to transfer well known concepts such as minors, tree decompositions, or planarity into the coarse setting. Shadowing this graph-theoretic development there is also notable interest in reproducing well-known algorithmic results, such as Max-Disjoint s-t-Path (Menger's theorem). \n\n\n\nThe coarse version of Menger's theorem here says that for a graph G, a distance parameter d, and vertex sets S,T there always exists a k for which one can route k S-T-paths with pairwise distance d, as well as find k balls of diameter O(d) whose removal separates S from T. Nguyen, Scott and Seymour were recently able to show that the coarse analogue of Menger's theorem does not hold in general graphs (arXiv:2508.14332), but a variant thereof does hold for the special case of planar graphs where all terminals are on a single face (arXiv:2509.07174). \n\n\n\nWe will revisit some of the recent developments in the area, as well as report on some work in progress developing an algorithmic analogue to the result of Nguyen et al.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1315
LOCATION:EEE Building, Elec204
END:VEVENT
END:VCALENDAR