Graph Theory Math 852 Spring 2010 Class Log

1. Jan 11, Mon. course overview and logistics; initial student survey; Sec 12.1: basic definitions of posets; axioms of order relations; examples; boolean lattice; comparability digraph; Hasse diagram; isomorphism and subposets; chains and antichains; width and height
2. Jan 13, Wed. guest lecturer Jamie Radcliffe; Dilworth theorem
3. Jan 15, Fri. guest lecturer Jamie Radcliffe; Sec 12.2: Sperner theorem; symmetric chain decompositions of 2^n; inductive construction; LYM inequality
Jan 18, Mon. Martin Luther King Day, no class.
4. Jan 20, Wed. definitions; bracket decomposition of 2^n; is the same as inductive construction
5. Jan 22, Fri. bounding the number of antichains in 2^n; Sec 11.2: intersecting families
6. Jan 25, Mon. Erdős-Ko-Rado theorem Sec 15.4: motivation of Möbius inversion by inclusion-exclusion; incidence functions; convolution and incidence algebra
7. Jan 27, Wed. incidence algebra as a matrix algebra; identity and zeta functions; inverses; Möbius μ function; Möbius inversion formula; for chains; for product of posets
8. Jan 29, Fri. inclusion-exclusion from Möbius inversion; Möbius function for divisor lattice; counting k-ary sequences with period exactly n; number of monic irreducible polynomials of degree n over F_q
9. Feb 1, Mon. partition lattice; Möbius function; Sec 13.1: block designs
10. Feb 3, Wed. incidence matrix; basic relations of parameters; Fisher's inequality; symmetric designs; block intersection sizes in symmetric designs; dual design
11. Feb 5, Fri. discussion of r is constant; conditions on parameters for symmetric designs: Schützenberger-Shrikhande and Bruck-Chowla-Ryser; nonexistence of symmetric (43,7,1)-design; Sec 13.2: projective planes; basic properties: dual notions; constant number of points and lines; definition of order; equivalence with symmetric designs
12. Feb 8, Mon. construction of finite Desarguesian projective plane; open question of existence for other orders; Sec 5.1: introduction to graphs; basic definitions; subgraph and induced subgraph; isomorphism
13. Feb 10, Wed. Petersen graph and properties; girth and circumference; hypercube; cartesian product of graphs; vertex transitive vs edge transitive; Sec 5.2: degree sum formula; counting subgraphs; application to the number of 5-cycles in Petersen graph
14. Feb 12, Fri. graphic sequences; Havel-Hakimi thm; 2-switches; can transform between graphs with same degree sequence using 2-switches; every graph has a bipartite subgraph with at least half the edges
15. Feb 15, Mon. maxmimum number of edges in a triangle-free graph; basic definitions of digraphs; tournaments; every tournament has a king; Sec 5.3: walks, paths, and connectivity; equivalence relation
16. Feb 17, Wed. König thm characterizing bipartite graphs; cut-vertices and cut-edges; use of maximal paths
17. Feb 19, Fri. Königsberg bridge problem; Eulerian circuits; characterization of Eulerian graphs; strongly and weakly connected digraphs; Eulerian digraphs; number of pencil lifts needed to draw a graph; Chinese Postman problem
18. Feb 22, Mon. Sec 5.4: trees; basic properties; characterizations; spanning trees; edge exchange property
19. Feb 24, Wed. Kruskal's algorithm; proof; Sec 15.2: counting spanning trees; edge contraction; recurrence; Matrix Tree thm; inductive proof
Feb 25, Thurs. Test #1
20. Feb 26, Fri. No class.
21. Mar 1, Mon. guest lecturer Tyler Seacrest; Sec 5.4: distance and related definitions; center of a tree; Moore bound; Sec 6.1: matchings
22. Mar 3, Wed. guest lecturer Tyler Seacrest; bipartite matching and systems of distinct representatives; Hall theorem with induction proof; marriage theorem
23. Mar 5, Fri. Ore defect formula; vertex covers; König-Egeváry thm; relations among independence number, matching number, vertex covers, and edge covers
24. Mar 8, Mon. finished Gallai theorem; application to bipartite graphs; Sec 6.2: matchings in general graphs; Tutte's condition; deficiency; parity lemma; properties of maximal maximum deficiency set
25. Mar 10, Wed. proof of Berge-Tutte formula; Tutte's 1-factor thm; Petersen thm; Plesnik thm
26. Mar 12, Fri. Sec 6.3: algorithmic issues; M-augmenting paths; symmetric difference of matchings; finding matchings in bipartite graphs
Mar 14 to Mar 19. Spring break - no classes.
27. Mar 22, Mon. maximum weighted bipartite matching; example; informal feedback survey
28. Mar 24, Wed. discussion of informal feedback survey; Sec 7.1: separating sets, k-connected, and connectivity; connectivity of complete graphs; minimum degree bound; Harary graphs; connectivity of hypercubes
29. Mar 26, Fri. disconnecting sets, k-edge-connected, and edge connectivity; edge connectivity of complete graphs; edge cuts; minimum degree bound; Whitney thm; size of disconnected piece when kappa'<delta; case of diameter 2
30. Mar 29, Mon. Sec 7.2: statement of Menger thm; Pym thm; proof; proof of Menger via Pym for vertex connectivity in the undirected and directed cases
31. Mar 31, Wed. line graphs; edge version of Menger thm; line digraphs; global versions of Menger thm; expansion lemma
32. Apr 2, Fri. fan lemma; Dirac thm; Network Flow handout: networks; flows; cuts; weak duality
33. Apr 5, Mon. f-augmenting paths; Ford-Fulkerson algorithm; Max Flow-Min Cut thm; integrality; proof of edge Menger thm for digraphs; transformations; common system of distinct representatives
34. Apr 7, Wed. Sec 8.1: coloring definitions; clique number; basic bounds; greedy coloring; k-degeneracy; Szekeres-Wilf theorem; Brooks thm
35. Apr 9, Fri. Mycielski construction; maxmimum chromatic number of triangle-free graphs; Sec 11.1: Turán graph
36. Apr 12, Mon. Turáan thm; Sec 8.2: color critical graphs; structural properties; k-critical graphs are k-edge-connected
37. Apr 14, Wed. Sec 8.3: edge coloring; connection to line graph; basic bounds; extending color fans
Apr 15, Thurs. Test #2
38. Apr 16, Fri. Vizing thm for simple graphs; fat triangle and Shannon thm; statement of multigraph Vizing thm; Sec 9.1: embeddings, planar multigraphs, and plane multigraphs; dual and properties
39. Apr 19, Mon. Euler's formula; bound on number of edges in planar simple graphs; classification of the Platonic solids
40. Apr 21, Wed. Sec 9.2: subdivisions; Kuratowski thm
41. Apr 23, Fri. Sec 9.3: coloring of planar graphs; 5-degeneracy; Five Color thm; discussion of Four Color thm; evaluations
42. Apr 26, Mon. Sec 7.3: Hamiltonian cycles; necessary conditions; Dirac thm; Ore lemma and thm; closure; Chvátal thm
43. Apr 28, Wed. Sec 7.3: Hamiltonicity approach to the Four Color thm; Tait thm; Grinberg thm; Tutte graph
44. Apr 30, Fri. No lecture.
May 5, Wed, 10:00am-12:00pm. Final Exam

    Back This page last modified .