NMAG403 Kombinatorika - 2025/26

Monday 9:00 - KKA

Recitations Monday 10:40 - KKA

Literature:
R. Diestel: Graph Thoery, available on-line on flooved.
T. Valla: Skripticka z kombinatoriky
M. Hall: Combinatorial Theory, Wiley 1986
My handouts from previous years might be useful, they can be found in SIS.

SEP 29, 2025
Recap of what you should remember from previous courses on Discrete Math and Graph Theory
Network flows, connectivity measures of graphs (vertex- and edge-connectivity), planar graphs.
Hall's Theorem on Systems of Distinct Representatives
Set systems, systems of distinct representatives, Hall's theorem. Applications - matchings in bipartite graphs, extending Latin rectangles to Latin squares. Maximum matching and minimum vertex cover in bipartite graphs. Independent sets and covering lines in matrices (on the way to Birkhoff Theorem on bistochastic matrices, to be done during the recitations).

SEP 29, 2025 recitations