Structure in sparse graphs
Structure in sparse graphs
-
Nemanja Draganic, Bocconi University
Fine Hall 224
Suppose G is a graph for which the only assumption is a lower bound on its average degree, even one as weak as a fixed absolute constant. What kind of structure can we still guarantee? For instance, must G contain a cycle whose length is a power of two, a subdivision of a clique in which all subdivision paths have the same length, or a cycle with at least as many chords as vertices?
There has been significant progress on questions of this kind, particularly over the past five years. In this talk, we will discuss some of these developments, as well as our recent work toward a new unified approach to such problems.