MATH 582

STRUCTURE OF GRAPHS, Spring 2012

Summary of Lectures

This page contains a summary of the lectures in this course for Spring 2012. It lists only the topics discussed in each lecture. The text provides extensive discussion and additional material, so no additional notes are given here.


1 1/18We: introduction (overview of topics)

Chapter 6: Elementary Structural Concepts
2 1/20Fr: Matrix Tree background, Matrix Arborescence Theorem, counting Eulerian circuits
3 1/23Mo: graceful labelings (hypercubes), T-decomposition (girth vs diameter), intro to packing
4 1/25We: graph packing (Sauer-Spencer Thms, Bollobas-Eldridge Conj, start of Hajnal-Szemeredi proof)
5 1/27Fr: completion of Hajnal-Szemeredi Theorem
6 1/30Mo: graphic and bigraphic lists (2-switch, Aigner-Triesch method)
7 2/01We: potentially k-edge-connected lists, Kundu's Theorem, vertex ptns under degree constraints
8 2/03Fr: graph reconstruction (counting arguments, disconnected graphs, tree preliminaries)
9 2/06Mo: reconstruction (trees, spanning subgraphs, almost all graphs), edge-reconstruction
10 2/08We: product dimension (examples and bounds)

Chapter 7: Connection and Cycles
11 2/10Fr: connectivity of cartesian products, Edmonds' Branching Theorem
12 2/13Mo: Edmonds to Menger, Itai-Rodeh Conjecture, statement of Lucchesi-Younger Theorem, k-linked graphs, forced subdivisions
13 2/15We: reminder of ear decomposition, contraction lemma & 3-connected graphs (sketch of Tutte characterization), Halin example, k-valent vertices in minimally k-connected graphs (Mader etc.)
14 2/17Fr: Gyori-Lovasz Theorem, gossip problem
15 2/20Mo: Nash-Williams Orientation Theorem, idea of Mader's average degree 4k guaranteeing k-connected subgraph
16 2/22We: toughness (9/4-tough non-Hamiltonian), k-closure,
17 2/24Fr: density conditions (Bondy-Chvatal condition for t dominating verts, Las Vergnas condition), Lu's Theorem strengthening Chvatal-Erdos
18 2/27Mo: circumference (Erdos-Gallai Thm, Bondy's Lemma on long paths, long-cycle version of Ore's Theorem, Fan's Theorem), digraphs skipped (Ghoula-Houri, Meyniel)
19 2/29We: stronger conclusions (Thomason lollipop, Fink on hypercubes, Bondy pancyclicity)
20 3/02Fr: Jackson's Theorem (regular graphs), claw-free graphs skipped (Matthews-Sumner Conjecture, Ryjacek closure)

Chapter 8: Planar and non-planar graphs
21 3/05Mo: MacLane/Whitney planarity criteria, Schnyder labeling & grid embedding (overview)
22 3/07We: Schnyder labelings (proofs)
23 3/09Fr: Reducibility of Birkhoff diamond, discharging technique (Franklin, Cranston edge-choosability, skipped Borodin's light triangles)
24 3/12Mo: dynamic coloring by discharging, Tait's and Grinberg's Theorems and Hamiltonicity in planar graphs (brief mention)
25 3/14We: Grotzsch's Theorem, Steinberg's Conjecture (Borodin-Sanders-Zhao), brief mention of Jaeger's Conjecture (circular coloring of planar graphs with large girth)
26 3/16Fr: Lipton-Tarjan Separator Theorem, skipped applications
27 3/26Mo: #perfect matchings in planar bipartite graphs (Kasteleyn), start interval number
28 3/28We: interval number and total interval number of planar graphs, thickness
29 3/30Fr: outerplanar thickness, pagenumber, start of crossing number
30 4/02Mo: crossing number and application, t-linear crossing numbers
31 4/04We: genus, Heawood's Formula
32 4/06Fr: rotation schemes and voltage graphs

Chapter 9: Graph minors and related topics
33 4/09Mo: graph minors, testing minors, K4-minor-free = 2-decomposable
34 4/11We: treewidth characterizations, cops-and-robber
35 4/13Fr: brambles, min/max for treewidth
36 4/16Mo: approach to graph minor theorem, well-quasi-ordering for trees
37 4/18We: cycle covers and flows
38 4/20Fr: flows on surfaces, 8-flow theorem
39 4/23Mo: modular flows, 6-flow theorem

Chapter 10: Algebraic aspects of graphs
40 4/25We: eigenvalues (basics, bipartite graphs, diameter)
41 4/26Th: interlacing, bounds on largest eigenvalue, eigenvalues of regular graphs
42 4/30Mo: strongly regular graphs (Moore graphs, Friendship Theorem)
43 5/02We: Laplacian eigenvalues (algebraic connectivity, spanning trees, expansion properties)