Please note: This seminar will take place in DC 2568 and online.
Greg Bodwin, Assistant Professor
Electrical Engineering & Computer Science, University of Michigan
In extremal combinatorics, a Turán-type problem is one that asks for the maximum possible size of a graph that avoids one or more forbidden subgraphs. These are named for Turán’s Theorem from 1941, which solves the problem for cliques.
In theoretical computer science, a graph metric sparsification problem is one that asks how many edges we can generally remove from a graph while approximately preserving its distance or reachability properties.
We will survey a recent line of work connecting these areas, which approaches graph metric sparsification through the lens of forbidden subgraphs. No prior knowledge of either area is assumed.
To attend this seminar in person, please go to DC 2568. You can also attend virtually on Zoom.