Department of

Mathematics


Seminar Calendar
for events the day of Saturday, November 14, 2015.

     .
events for the
events containing  

(Requires a password.)
More information on this calendar program is available.
Questions regarding events or the calendar should be directed to Tori Corkery.
     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

1:00 pm in Altgeld Hall,Saturday, November 14, 2015

To Be Announced

Kent Quanrud   [email]

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).