Topics in Discrete Mathematics: Structural Graph Theory Math 958 Fall 2011 Class Log

  1. Aug 22, Mon. course overview and logistics; Sec 6.1: Matrix Tree Thm; proof
  2. Aug 24, Wed. counting out-trees in a digraph; Matrix Arborenscence Thm; proof
  3. Aug 26, Fri. finished proof; one-to-many bijection between rooted in-trees and Eulerian circuits.
  4. Aug 29, Mon. BEST Thm; graph packing; examples; counting arguments
  5. Aug 31, Wed. Sauer-Spencer Thm; proof; sharpness; Bollobás-Eldridge-Catlin Conj; statement of Hajnal-Szemerédi Thm
  6. Sep 2, Fri. proof of Hajnal-Szemerédi Thm
    Sep 5, Mon. Labor Day — no class.
  7. Sep 7, Wed. finished proof of Hajnal-Szemerédi Thm
  8. Sep 9, Fri. Sec 6.2: vertex degrees; Kleitman-Wang Lemma; Havel-Hakimi Thm; statement of Erdős-Gallai
  9. Sep 12, Mon. constructive proof of Erdős-Gallai; dominance order; graphic sequences form an ideal
  10. Sep 14, Wed. Aigner-Triesch method; Gale-Ryser thm
  11. Sep 16, Fri. potentially-graphic vs forcibly graphic; examples; Kundu thm; Sec 8.1: Euler's Formula; statement of Kuratowski thm and Wagner thm; difference between subdivision and minor
  12. Sep 19, Mon. cycle space and bond space; equivalence of 2-basis and planarity
  13. Sep 21, Wed. using Euler's Formula to prove nonplanarity; abstract dual; Whitney thm; straight-line embeddings; barycentric coordinates
  14. Sep 23, Fri. barycentric representation gives a planar straight-line embedding; Schnyder labelings; existence of contractible edges
  15. Sep 26, Mon. existence of Schnyder labelings; arise inductively; Uniform Angle Lemma
  16. Sep 28, Wed. proof of Uniform Angle Lemma; barycentric coordinates from Schnyder labeling; gives barycentric representation
  17. Sep 30, Fri. Sec 8.2: 6-color thm; 5-color thm; overview of proof of 4-color thm; unavoidable configurations and reducibility; list coloring; example showing strict inequality of chromatic number and list-chromatic number
  18. Oct 3, Mon. No class.
  19. Oct 5, Wed. planar graphs are 5-choosable; discharging; prop by Franklin
  20. Oct 7, Fri. discharging example of Cranston; edge-choosability
  21. Oct 10, Mon. statement of Grötzsch's thm; reducible configurations (safe faces)
  22. Oct 12, Wed. configurations are unavoidable
  23. Oct 14, Fri. Sarah Behrens: more conditions for graphic sequences
    Oct 17, Mon. Fall Break — no class.
  24. Oct 19, Wed. Sec 8.5: higher surfaces; genus; 2-cell embeddings; Euler's formula
  25. Oct 21, Fri. edge bound; Heawood formula; Sec 9.1: minors and subdivisions; historical context
  26. Oct 24, Mon. Hadwiger and Hajóos conjectures; clique sums; K4-minor-free graphs; discussion of K5-minor-free graphs
  27. Oct 26, Wed. Guest lecturer Michael Ferrara of the University of Colorado Denver: degree conditions for H-linkages
  28. Oct 28, Fri. Lauren Keough: characterization of sharpness examples for Sauer-Spencer
  29. Oct 31, Mon. Sec 7.1: large average degree (or min degree) forces large complete subdivisions; definition of k-linked
  30. Nov 2, Wed. large connectivity implies k-linked; Sec 9.1: definition of treewidth
  31. Nov 4, Fri. examples; upper bound of treewidth of nxn grid; relation to connectivity; equivalent formulations of treewidth
  32. Nov 7, Mon. cops-and-robber; grid;
  33. Nov 9, Wed. brambles; robber strategy using brambles; statement of min-max theorem; Sec 9.2: well-qasi-orders; structure of proof of Graph Minor Theorem
  34. Nov 11, Fri. Derrick Stolee: Ryjacek closure
  35. Nov 14, Mon. products and powers of WQOs are also WQO
  36. Nov 16, Wed. trees under the rooted topological minor order are WQO; Sec 10.3: extremal numbers; statement of Turán; statement of Erdős–Stone thm; Erdős–Simonovits thm
  37. Nov 18, Fri. Nora Youngs: precoloring extensions of graphs
  38. Nov 21, Mon. statement of Szemerédi Regulary Lemma; Embedding Lemma and proof
    Nov 23-25, Wed-Fri. Thanksgiving Break — no class.
  39. Nov 28, Mon. finished proof of Embedding Lemma; proof of Erdős–Stone thm
  40. Nov 30, Wed. proof of Regularity Lemma
  41. Dec 2, Fri. No class.
  42. Dec 5, Mon. James Carraher: planar separators
  43. Dec 7, Wed. Jeremy Trageser: graphic sequences with small gaps
  44. Dec 9, Fri. Zach Roth: voltage graphs

    Back This page last modified .