Math 7405 Advanced Graph Theory Spring 2016 Class Log

1. Jan 20, Wed. course overview and logistics; initial student survey; Sec 3.4: list coloring, basic definitions, simple bounds; separation of chromatic and list chromatic numbers; greedy coloring
2. Jan 25, Mon. degree choosability; conditions that imply degree choosability
3. Jan 27, Wed. characterization of degree choosable graphs, Gallai trees; Brooks-type theorem for list chromatic number; connection between non-k-choosable bipartite graphs and non-2-colorable k-uniform hypergraphs
4. Feb 1, Mon. finished connection between non-k-choosable bipartite graphs and non-2-colorable k-uniform hypergraphs; upper bound on list chromatic number of balanced complete bipartite graphs; started lower bound on list chromatic number of graphs in terms of average degree, reduced to bipartite graphs with specified min degree
5. Feb 3, Wed. finished lower bound on list chromatic number of graphs in terms of average degree for bipartite graphs
6. Feb 8, Mon. planar graphs are 5-choosable; kernels and kernel-perfect digraphs; implication for choosability
7. Feb 10, Wed. Thm 2.4.39 every digraph with no odd cycle has a kernel; bipartite planar graphs are 3-choosable
8. Feb 15, Mon. edge list coloring; List Coloring Conj; Galvin proof of Dinitz conjecture
9. Feb 17, Wed. Combinatorial Nullstellensatz; statement and proof
10. Feb 22, Mon. graph polynomial; interpretation of coefficients in terms of orientations
11. Feb 24, Wed. circulations; Alon-Tarsi theorem; list-3-coloring the squares of cycles
12. Feb 29, Mon. Sec 3.1: color critical graphs; basic properties: min degree, edge-connectivity, every vertex cut is a clique; generalized Hajos construction; conjectured edge-bound
13. Mar 2, Wed. Nathan presented on applications of the Combinatorial Nullstellensatz
14. Mar 7, Mon. potential method for proving edge-bound of 4-critical graphs
15. Mar 9, Wed. continued proof; application to Grotzsch thm
16. Mar 14, Mon. class cancelled
17. Mar 16, Wed. Jason presented on expected run time of backtracking for coloring; column generation algorithm for coloring
18. Mar 28, Mon. guest Peter Erdos; lecture on sampling degree sequences via Markov Chain Monte Carlo
19. Mar 30, Wed. Sec 3.6: discharging; 6-color thm and 5-color thm viewed as discharging proofs; typical charges on planar graphs; planar graphs of girth at least 6 using balanced charging
20. Apr 4, Mon. discharging proof for bound on list chromatic number of the square, under max degree and Mad conditions
21. Apr 6, Wed. Duong presented two short proofs of Grotzsch's thm
22. Apr 11, Mon. Vizing's Planar Graph Conj; proof towards that
23. Apr 13, Wed. list choosability of planar graphs
24. Apr 18, Mon. Luke presented on the best-known partial result toward Steinberg's conjecture
25. Apr 20, Wed. Chase presented on Kastelyn's method for counting perfect matchings in planar graphs
26. Apr 25, Mon. Regularity Lemma; Embedding Lemma
27. Apr 27, Wed. proof of Erdos-Stone; proof sketch of the Regularity Lemma
28. May 2, Mon. Eric presented on graph Ramsey numbers using the Regularity Lemma
29. May 4, Wed. Removal Lemma; Roth's theorem on 3-term arithmetic progressions; corners in matrices

    Back This page last modified .