Structure for Dense Graphs

Course Number: 
Hours - Lecture: 
Hours - Total Credit: 
Typical Scheduling: 
Not Regularly Scheduled

Graph theory (ideally on the level of MATH 6014, but any course covering graph connectivity and planar graphs should suffice)

Topic Outline: 

Structural graph theory has traditionally focused on classes of graphs that are 'sparse' rather than 'dense' (that is, have few edges rather than many edges). We will study this paradigm, focusing on modern developments for dense graphs. Along the way we will see connections to algorithms and complexity, discrete geometry, and logic. In each unit, we first introduce standard techniques for sparse graphs, and then we study their 'dense analogs'. Specific topics include connectivity, tree width and related width parameters, graphs on surfaces, graph minors, bounded expansion, and nowhere denseness, in that order. Their 'dense analogs' include, respectively: rank-connectivity, clique width, geometric intersection graphs, vertex-minors, bounded flip-width, and monadic dependence.