MATH 418

STRUCTURE OF GRAPHS, Spring 2001

Summary of Lectures

This page contains a summary of the lectures in this course for Spring 2001 (the course number was changed to 582 in Fall 2004). It lists only the topics discussed in each lecture, and it may be incomplete because it was not constructed until Dec 25, 2002. The text provides extensive discussion and additional material, so no additional notes are given here.


1 1/17We: introduction (overview of topics)
2 1/19Fr: Matrix Tree Theorem, Matrix Arborescence Theorem
3 1/22Mo: counting Eulerian circuits, graceful labelings (hypercubes)
4 1/24We: tree decomposition, degree sequences
5 1/26Fr: CANCELED (Univ power failure)
6 1/29Mo: Erdos-Gallai sufficiency by Aigner-Triesch method, Edmonds characterization of potentially k-connected sequences
7 1/31We: threshold sequences, reconstruction problem (counting arguments, parameters)
8 2/02Fr: reconstruction of trees and almost all graphs, edge-reconstruction
9 2/05Mo: isometric embedding
10 2/07We: metric representation, product dimension
11 2/09Fr: product dimension, forcibly k-connected sequences
12 2/12Mo: Edmonds' Branching Theorem
13 2/14We: Lucchesi-Younger, Thomassen contraction lemma
14 2/16Fr: Tutte 3-connected characterization, Halin minimal k-connected graphs
15 2/19Mo: Mader minimal k-connected graphs, motivate Gyori-Lovasz Theorem
16 2/21We: Gyori-Lovasz proof
17 2/23Fr: Nash-Williams Orientation Theorem
18 2/26Mo: Hamiltonian graphs (toughness, k-closure, Las Vergnas condition)
19 2/28We: Bondy-Chvatal condition for t dominating verts, Lu's Theorem (strengthening Chvatal-Erdos)
20 2/30Fr: Lu's Theorem (proof)
21 3/05Mo: Erdos-Woodall extremal result on circumference, Bondy's Lemma on long paths
22 3/07We: Fan's Theorem on Hamiltonian cycles, gossip problem
23 3/09Fr: planarity review: dual graphs, Euler's Formula, Kuratowski's Theorem
24 3/19Mo: Lipton-Tarjan Separator Theorem
25 3/21We: application of separator theorem (pebbling, independent sets)
26 3/23Fr: coloring of planar graphs (idea of discharging)
27 3/26Mo: reducibility of Birkhoff diamond, Thomassen proof of Grotzsch's Theorem (sketch)
28 3/28We: Borodin discharging argument for 3-coloring, start genus
29 3/30Fr: genus, Heawood's Formula
30 4/02Mo: voltage graphs
31 4/04We: thickness and pagenumber
32 4/06Fr: crossing number
33 4/09Mo: minors, begin treewidth
34 4/11We: treewidth characterizations, cops in helicopters
35 4/13Fr: graph minor approach, well-quasi-ordering
36 4/16Mo: cycle covers and flows
37 4/18We: 8-flow theorem
38 4/20Fr: modular flows, 6-flow theorem
39 4/23Mo: eigenvalues (up to interlacing)
40 4/25We: bounds on largest eigenvalue, eigenvalues of regular graphs
41 4/27Fr: eigenvalues and expanders, strongly regular graphs (Friendship Theorem)
42 4/30Mo: chromatic polynomial, with relation to rank and Tutte polynomials
43 5/04Fr: quasi-random graphs (sketch of equivalent properties)