MATH 582

STRUCTURE OF GRAPHS, Spring 2008

Summary of Lectures

This page contains a summary of the lectures in this course for Spring 2008. 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/14Mo: introduction (overview of topics)

Chapter 6: Elementary Structural Concepts
2 1/16We: Matrix Tree background, Matrix Arborescence Theorem, counting Eulerian circuits
3 1/18Fr: graceful labelings (hypercubes), T-decomposition (girth vs diameter)
4 1/23We: graph packing (Sauer-Spencer Thms, Bollobas-Eldridge Conj)
5 1/25Fr: Hajnal-Szemeredi Theorem (new proof)
6 1/28Mo: graphic lists (2-switch, Aigner-Triesch method),
7 1/30We: potentially k-edge-connected lists, vertex ptns under maximum or minimum degree constraints
8 2/01Fr: graph reconstruction (counting arguments, disconnected graphs, tree preliminaries)
9 2/04Mo: reconstruction (trees, almost all graphs), edge-reconstruction
10 2/06We: isometric embedding & metric representation
11 2/08Fr: product dimension

Chapter 7: Connection and Cycles
12 2/11Mo: Edmonds' Branching Theorem and applications, sketch of Lucchesi-Younger Theorem
13 2/13We: k-linked graphs, forced subdivisions
14 2/15Fr: reminder of ear decomposition, contraction lemma & 3-connected graphs (sketch of Tutte characterization), Halin example, minimally k-connected graphs (Mader etc.)
15 2/18Mo: Gyori-Lovasz Theorem, proof for gossip theorem
16 2/20We: Nash-Williams Orientation Theorem
17 2/22Fr: toughness (9/4-tough non-Hamiltonian), k-closure, density conditions (Bondy-Chvatal condition for t dominating verts, Las Vergnas condition)
18 2/25Mo: Lu's Theorem strengthening Chvatal-Erdos (skipping hard case)
19 2/27We: Hamiltonian claw-free graphs (Matthews-Sumner Conjecture, Ryjacek closure)
20 2/29Fr: circumference (Erdos-Gallai Thm, Bondy's Lemma on long paths, Bermond's Theorem, Fan's Theorem), digraphs skipped (Ghoula-Houri, Meyniel)

Chapter 8: Planar and non-planar graphs
21 3/03Mo: MacLane/Whitney planarity criteria, Schnyder labeling & grid embedding overview
22 3/05We: Schnyder labelings (proofs)
23 3/07Fr: Reducibility of Birkhoff diamond, discharging technique (Wernicke, Borodin's light triangles)
Note: skipped Tait's and Grinberg's Theorems and Hamiltonicity in planar graphs
24 3/10Mo: Grotzsch's Theorem, Thomassen 3-colorability of planar graphs with girth at least 5
25 3/12We: Jaeger's Conjecture (circular coloring of planar graphs with large girth)
26 3/14Fr: Lipton-Tarjan Separator Theorem, sketch of application to independent sets (skipped pebbling)
27 3/24Mo: counting perfect matchings in planar bipartite graphs (Kasteleyn)
28 3/26We: interval number and total interval number of planar graphs
29 3/27Th: thickness and pagenumber
30 3/31Mo: crossing number and application
31 4/02We: t-linear crossing numbers, genus, Heawood's Formula
32 4/04Fr: voltage graphs

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

Chapter 10: Algebraic aspects of graphs
40 4/23We: eigenvalues (basics, bipartite graphs, diameter)
41 4/25Fr: interlacing, bounds on largest eigenvalue, eigenvalues of regular graphs
42 4/28Mo: eigenvalues and expanders, strongly regular graphs (Friendship Theorem)
43 4/30We: chromatic polynomial, with relation to rank and Tutte polynomials