Department of

October 2015 November 2015 December 2015 Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa 1 2 3 1 2 3 4 5 6 7 1 2 3 4 5 4 5 6 7 8 9 10 8 9 10 11 12 13 14 6 7 8 9 10 11 12 11 12 13 14 15 16 17 15 16 17 18 19 20 21 13 14 15 16 17 18 19 18 19 20 21 22 23 24 22 23 24 25 26 27 28 20 21 22 23 24 25 26 25 26 27 28 29 30 31 29 30 27 28 29 30 31

Saturday, November 14, 2015

**Abstract:** In optimization, the edge density of a graph (i.e., the ratio of the number of edges to vertices) does not capture the computational intractability of graph problems. For example, planar graphs and constant degree expanders both have edge density bounded by a constant, but in combinatorial optimization the former is generally more tractable than the latter. A more refined approach is the notion of expansion under minors, developed recently by Nešetřil and Ossona de Mendez, which considers not only the edge density of a graph but the edge densities of its shallow minors. In this theory, planar graphs have small (constant) expansion under minors while expanders have large (exponential) expansion under minors. In this survey-style talk I will introduce the theory of expansion under minors and discuss some of its applications. The talk is motivated by recent work with Sariel Har-Peled in which we obtain polynomial time approximation schemes for problems such as minimum dominating set on classes of graphs with polynomial expansion (available at http://illinois.edu/~quanrud2/papers/low_density.pdf).