2023 Spring
Combinatorial Methods, PPKE, Wednesday 8:30-10:00
Lecture Notes.
Syllabus and details of course
Info on exam
Week 1
Mar 7, Tuesday: Interval Systems. Chapter 1 of the textbook.
Week 2
Mar 14, Tuesday: Intersection graphs, interval graphs, sequential coloring. Chapter 2 of textbook.
Week 3
Mar 21, Tuesday: Helly property of subtrees of a tree. Chordal graphs, simplicial vertex, simplicial vertex order.
Equivalence of the definition of chordal graphs to the existence of simplicial order.
Algorithms: finding a simplicial order if it exists, independent sets and clique coverings, chromatic number and max clique.
Week 4
Mar 28, Tuesday: tree decomposition, nice tree decomposition, treewidth of a graph. Dynamic programming: subset-sum problem.
Week 5
Apr 4, Tuesday: Midterm
Week 6
Apr 11, Tuesday: largest independent set in graphs with bounded treewidth, bipartite graphs, equivalence to having no odd cycles,
alternating / augmenting paths, maximum matching
Week 7
Apr 18, Tuesday: Hall's condition and Hall's theorem for matching that covers the smaller part of a bipartite graph.
systems of distinct representatives, stable matchings.
Week 8
Apr 25, Tuesday: Maximum cut problem, for any graph G, there exists a cut with half the edges (2 algo, and a probabilistic proof).
Precolor and list coloring problem. k-choosability, list-chromatic number. Relations of chromatic, list-chromatic and coloring numbers.
Kernels in DAGs and directed bipartite graphs.
Week 9
May 2, Tuesday: List coloring of graph with orientation having kernels for all induced subgraphs. Edge-decompositions: connected graphs into P_3.
Complete graph to matching, Hamiltonian paths, Hamiltonian cycles, complete bipartite graphs, cliques of fixed size.
Week 10
May 9, Tuesday: Projective planes: axioms and consequences. Affine planes.
Week 11
May 16, Tuesday: Turán problems. Mantel's and Turán's theorem. Forbidden cycles of length four.
Week 12
May 23, Tuesday: Final exam