Seminars

View all Seminars  |  Download ICal for this event

How 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