1. Jan 7, Mon.
course overview and logistics; initial student survey;
Sec 5.1: basic concepts in graph theory; definitions, isomorphism, subgraph and induced subgraph; common graph families; Petersen graph
2. Jan 9, Wed. cartesian (box) product; hypercube; Sec 5.2: degree sum formula; counting nested subgraphs; application to the number of 5-cycles in Petersen graph; degree sequences; characterization for multigraphs allowing loops; graphic sequences; statement of Havel-Hakimi; easy direction 3. Jan 11, Fri. proof of Havel-Hakimi; 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; maxmimum number of edges in a triangle-free graph 4. Jan 14, Mon. proof of Mantel thm; basic definitions of digraphs; tournaments; every tournament has a king; Sec 5.3: walks and paths; equivalence relation; connected graphs; strongly connected and weakly connected digraphs 5. Jan 16, Wed. cut vertices and cut edges; use of maximal paths; König thm characterizing bipartite graphs; Königsberg bridge problem; eulerian circuits; 6. Jan 18, Fri. proof of characterization of eulerian graphs; decompositions into cycles; drawing graphs with minimum strokes; Chinese Postman Problem; Sec 5.4: trees; basic properties; characterizations Jan 21, Mon. Martin Luther King Day, no class. 7. Jan 23, Wed. more basic properties of trees; spanning trees; edge exchange property; minimum weight spanning trees; Prim and Kruskal algorithms; proof of correctness of Kruskal algorithm 8. Jan 25, Fri. Sec 15.2: counting spanning trees; edge contraction; recurrence; Matrix Tree thm; inductive proof; Sec 1.3: Cayley's formula for the number of labeled trees; proof 9. Jan 28, Mon. Sec 5.4: distance and related definitions; center of a tree; Sec 6.1: bipartite matching and systems of distinct representatives; Hall theorem with induction proof; marriage theorem 10. Jan 31, Wed. Ore defect formula; vertex covers; König-Egerváry thm; relations among independence number, matching number, vertex covers, and edge covers; Gallai theorem 11. Feb 1, Fri. Sec 6.3: algorithmic issues; symmetric difference of matchings; M-augmenting paths; maximum weighted bipartite matching 12. Feb 4, Mon. Sec 6.2: Tutte's 1-factor thm; deficiency; Berge-Tutte formula; proof 13. Feb 6, Wed. Petersen's thm on 1-factors in cubic graphs with no cut-edge; Plesnik generalization; Petersen's 2-factor thm; f-factors; transformation showing equivalent to 1-factors Sec 7.1: separating sets, k-connected, connectivity; examples, including complete graph; minimum degree bound; minimum number of edges in a k-connected graph on n vertices 14. Feb 8, Fri. Harary graph; connectivity of hypercube; vertex k-splits; disconnecting sets, k-edge-connected, and edge connectivity; edge connectivity of complete graphs; edge cuts; minimum degree bound; Whitney thm 15. Feb 11, Mon. size of disconnected piece when kappa'<delta; case of diameter 2 Sec 7.2: statement of Menger thm; Pym thm; proof 16. Feb 13, Wed. proof of Menger via Pym for vertex connectivity in the undirected and directed cases; line graphs; edge version of Menger thm; line digraphs; directed edge version of Menger thm; global versions of Menger thm; Network Flow handout: networks; flows; f-augmenting paths 17. Feb 15, Fri. cuts; weak duality; Ford-Fulkerson algorithm; Max Flow-Min Cut thm; integrality; proof of edge Menger thm for digraphs; transformations; Gale-Ryser thm for bigraphic sequences 18. Feb 18, Mon. expansion lemma; fan lemma; Dirac thm; ear and weak ear decompositions; Robbins thm 19. Feb 20, Wed. Sec 7.3: Hamiltonian cycles; necessary conditions; Dirac thm; Ore lemma and thm; closure; Chvátal thm on degree sequences; Chvátal-Erdős thm Feb 20, Wed. Test #1 20. Feb 22, Fri. Sec 8.1: coloring definitions; basic bounds in terms of clique number, independence number, and maximum degree; Mycielski construction; greedy coloring; k-degeneracy; Szekeres-Wilf thm; Brooks thm 21. Feb 25, Mon. upper bound on chromatic number of triangle-free graphs; Minty's thm; Sec 11.1: statement of Turán's thm; Turán graphs maximize the number of edges among complete multipartite graphs 22. Feb 27, Wed. finished proof of Turán's thm; Sec 8.2: color critical graphs; structural properties; k-critical graphs are (k-1)-edge-connected; 23. Mar 1, Fri. Sec 8.3: edge-coloring; relation to line graph; basic bounds and examples; edge-chromatic number of complete graphs; edge-chromatic number of bipartite graphs; Vizing's thm and proof; statement of Shannon's thm and sharpness example 24. Mar 4, Mon. Sec 9.1: embeddings, planar multigraphs, and plane multigraphs; dual and properties; bipartite planar graphs; outerplanar graphs 25. Mar 6, Wed. strengthened induction hypothesis; Euler's formula; bound on number of edges in planar simple graphs; classification of the Platonic solids 26. Mar 8, Fri. Sec 9.2: subdivisions; Kuratowski's thm 27. Mar 11, Mon. finished proof of Kuratowski's thm; minors; Wagner's thm 28. Mar 13, Wed. higher genus surfaces; Wagner's conjecture; the Graph Minor Thm; Sec 9.3: coloring planar graphs; 5-degeneracy of planar graphs; Five Color Thm; discussion of Four Color Thm; Heawood formula 29. Mar 15, Fri. hamiltonicity approach to Four Color Thm; Tait thm; Grinberg thm; Tutte graph Mar 18, Mon. — Mar 22, Fri. Spring break, no class. 30. Mar 25, Mon. 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; Dilworth theorem 31. Mar 27, Wed. Sec 12.2: Sperner theorem; symmetric chain decompositions of 2^n; inductive construction 32. Mar 29, Fri. bracket decomposition of 2^n; is the same as inductive construction; bounding the number of antichains in 2^n; LYM inequality and proof of Sperner thm 33. Apr 1, Mon. Sec 12.3: linear extensions and realizers; dimension of a poset; simple examples; comparability graphs; characterization of posets with dimension at most 2; standard example 34. Apr 3, Wed. embedding a poset into a product of chains; monotonicity of dimension; dimension of boolean lattice; alternating cycles and chromatic number of hypergraphs 35. Apr 5, Fri. dimension and width; dimension is at most half the size of a poset 36. Apr 8, Mon. Sec 12.4: definition of lattices; examples of boolean, divisor, and partition lattices; Sec 11.2: intersecting families; Erdős-Ko-Rado theorem 37. Apr 10, Wed. Sec 11.2: shadows; colex order; binomial expansion of a natural number; Kruskal-Katona theorem Apr 10, Wed. Test #2 38. Apr 12, Fri. No class. 39. Apr 15, Mon. simplicial complexes; f-vectors; application of Kruskal-Katona thm; Sec 13.1: block designs; incidence matrix; basic relations of parameters; Fisher's inequality 40. Apr 17, Wed. symmetric designs; block intersection sizes in symmetric designs; dual design; conditions on parameters for symmetric designs: Schützenberger-Shrikhande and Bruck-Chowla-Ryser; nonexistence of symmetric (43,7,1)-design 41. Apr 19, Fri. Sec 13.2: projective planes; basic properties: dual notions; constant number of points and lines; definition of order; equivalence with symmetric designs; construction of finite Desarguesian projective plane; open question of existence for other orders 42. Apr 22, Mon. Sec 10.1: Pigeonhole Principle; Fermat's Sum of Two Squares theorem; Sec 10.2: Ramsey's theorem; Ramsey numbers; upper bound of 4^n on R(n,n) 43. Apr 24, Wed. basic probabilistic method; lower bound of 2^(n/2) for R(n,n); Happy End Problem; infinite ternary square-free word 44. Apr 26, Fri. No class. Apr 29, Mon, 10:00am-12:00pm. Final Exam |
Back | This page last modified . |