Math 582B: Graph Theory

MWF 12:30-1:30 CLK 316

Instructor: Isabella Novik

Office Hours: Friday 10-11 in PDL C-416 or by appointment

Course Outline

Homeworks

  • Homework #1, due 1/13/12
  • Homework #2, due 1/20/12
  • Homework #3, due 1/30/12
  • Homework #4, due 2/6/12
  • Homework #5, due 2/13/12
  • Homework #6, due 2/24/12
  • Homework #7, due 3/2/12
  • Homework #8, due 3/9/12

    • Topics discussed so far

  • Connectivity, Menger's theorem (January 4)
  • Applications of Menger's theorem; matchings in bipartite graphs (January 6)
  • Characterizations of 2-connected graphs; statement of the Linial-Lovasz-Wigderson theorem (January 9)
  • Introduction to matroids: independent sets, rank functions,... (January 11)
  • Two applications of Edmonds' matroid union theorem to decomposing a graph into trees (January 13)
  • Hall's and Rado's theorems (January 23)
  • The proof of Edmonds' matroid union theorem (January 25)
  • Introduction to planar graphs: Euler's formula; bounds on the number of edges; 5-colorability (January 27)
  • The Tarjan-Lipton theorem (January 30)
  • Sperner's lemma and a planar version of Menger's theorem (January 31)
  • The Koebe-Andreev-Thurston theorem and the Steinitz theorem (February 1 and 3)
  • Deriving the Tarjan-Lipton theorem from the Koebe-Andreev theorem (February 6)
  • The crossing theorem; statement of the Kuratowski theorem (February 8)
  • The proof of the Kuratowski theorem (February 10)
  • Extremal graph theory: forbidden paths and cycles (February 13)
  • Turan's theorem; estimating the maximum number of antipodal pairs of an n-element set in R^d (February 15)
  • The Zarankiewicz problem (February 17 and 22)
  • The Erdos-Stone theorem (February 24)
  • Ramsey Theory (February 27, 29)
  • Szemeredi's regularity lemma (March 2, 5)
  • Applications of the regularity lemma (March 7, 9)