Seminars
View all Seminars | Download ICal for this eventHow to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free Graphs
Series: Bangalore Theory Seminars
Speaker: Jonathan Conroy,Dartmouth College
Date/Time: Feb 05 11:00:00
Location: Online Talk-teams link follows
Abstract:
Roughly, an edge-weighted graph G has padding parameter β if for every ? >0, there is a stochastic partition of the vertices V(G) into clusters of diameter at most ? such that each ball of radius γ belongs to a single cluster with probability at least 1??β??γ/?.
In this talk, I will show that every K_r-minor-free graph has padding parameter O(log r), resolving a long standing open question. A key technical tool is a new structural result on minor-free graphs - the "buffered cop decomposition" - which is also helpful for a host of other problems in planar and minor-free graphs.
Talk is based on joint work with Arnold Filtser (Link and with Hsien-Chih Chang, Hung Le, Lazar Milenkovi?, Shay Solomon, and Cuong Tha (Link
Microsoft Teams link:
Link
We are grateful to the Kirani family (Link and the Walmart Center for Tech Excellence (Link for generously supporting this seminar series
Hosts: Rameesh Paul, Debajyoti Kar, KVN Sreenivas, Nirjhar Das, Rahul Madhavan