Combinatorial Methods, PPKE, Wednesday 8:30-10:00

Lecture Notes.

Syllabus and details of course

Info on exam

Mar 7, Tuesday: Interval Systems. Chapter 1 of the textbook.

Mar 14, Tuesday: Intersection graphs, interval graphs, sequential coloring. Chapter 2 of textbook.

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.

Mar 28, Tuesday: tree decomposition, nice tree decomposition, treewidth of a graph. Dynamic programming: subset-sum problem.

Apr 4, Tuesday: Midterm

Apr 11, Tuesday: largest independent set in graphs with bounded treewidth, bipartite graphs, equivalence to having no odd cycles,

alternating / augmenting paths, maximum matching

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.

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.

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.

May 9, Tuesday: Projective planes: axioms and consequences. Affine planes.

May 16, Tuesday: Turán problems. Mantel's and Turán's theorem. Forbidden cycles of length four.

May 23, Tuesday: Final exam