Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

This lecture intends to introduce areas that are closely connected to graph theory but usually do not fit into an introductory course. The algorithmic approach plays an important role in the solution of the studied problems.

Algorithmic proofs: greedy techniques, improving pahts, local improvements and elementary constructions

Stable matchings, the Gale-Shapley algorithm, lattice property of stable matchings. Applications: linking property of paths, Galvin's theorem, Alon-Tarsi theorem on the choosability of planar bipartite graphs, the Sands-Sauer-Woodrow theorem, kernels in acyclic digraphs.

Stable matchings on nonbipartite graphs: Irving's algorithm. Stable half-matchings and Scarf's lemma

Finding minimum cuts in graphs, the Nagamochi-Ibaraki algorithm (maxback order), simplicial graphs, simplicial vertices, list-colouring of simplicial graphs, Karger's algorithm

Representation of laminar families and of minimum cuts: the Gomory-Hu (cut equivalent) tree and the cactus-representation.

Tutte theorem, Tutte-Berge formula, Edmonds-Gallai structure theorem, factor critical graphs.

Lovász' theorem on splitting off, construction of 2k-edge-connected graphs, Nash-Williams'orientation theorem.

Circulations and flows. Hoffmann's theorem, algorithm for minimum-cost circulation.

Applications of the integrality lemma (edge-coloring of bipartite graphs, rounding property of flows and Baranyai's theorem).

In the semester: two midterm. The condition for the audit is that both midterms are succesful.

In the exam season: oral exam for those that have a valid audit. The final grade is based 40% on the midterms and 60% on the oral exam.

R. Diestel: Graph Theory

András Frank: Connections in Combinatorial Optimization