NMAG403 Kombinatorika - 2026/27

Tuesday 9:00 - K8

Recitations Tuesday 10:40 - K8

Literature:
R. Diestel: Graph Theory, 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.

Requirements for the exam All topics covered in the class (see the brief minutes from the sessions below).
The exam is oral. Typically you get 3 questions, one of which will be problem oriented to show that you can apply the skills acquired during the class to a slightly new situation; hints will be provided to the problem-oriented questions.
For a passing grade (3), you must know all definitions, theorems and the basic proofs.
For the B grade (2), you should know all proofs.
For the A grade (1), you must be able to apply the skills acquired during the class to solving a relatively new problem (with a possible hint from the examiner).

OCT 6, 2026
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 doubly stochastic matrices, to be done during the recitations).

OCT 6, 2026 recitations

Problems solved so far during the recitations

Problem	1	2	3	4	5	6	7	8	9	10	11	12	13	14
Date solved					10/6				10/6
Problem	31	32	33	34	35	36	37	38	39	40	41	42	43	44
Date solved