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