NMAG403 Kombinatorika - 2025/26

Monday 9:00 - KKA

Recitations Monday 10:40 - KKA

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) except the Abueida-Pike theorem from January 5, 2026 (you can use this theorem and its proof as a jolly-joker card to substitute for one of the questions).
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 the proofs.
For the A grade (1), you must be able to apply the skills to solving a relatively new problem (with a possible hint from the examiner).
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

OCT 6, 2025
Matchings in general graphs
Maximal, maximum and perfect matchings in a graph. Maximum matchings and augmenting paths. Tutte's theorem on the existence of a perfect matching in a graph. Petersen's theorem on perfect matchings in cubic edge-2-connected graphs.

OCT 6, 2025 homework I

OCT 13, 2025
Edmonds's algorithm for maximum matching in a general graph

OCT 13, 2025 recitations

OCT 20, 2025
Chooseability of graphs
List colorings and chooseability. Chooseability of planar graphs. Bounds on chooseability via orientations with kernels.

OCT 20, 2025 recitations

OCT 27, 2025
Graph Coloring II
Coloring graphs on surfaces of higher (orientable) genus - Heawood Theorem. Edge coloring - Vizing Theorem.

OCT 27, 2025 recitations and Homework 2

NOV 3, 2025
Planar graphs
Some lemmas on drawings of planar graphs. Lemma about edge-contraction in 3-connected graphs. Proof of Kuratowski theorem.

NOV 3, 2025 recitations

NOV 10, 2025
Hamiltonian cycles
Sufficient conditions for Hamiltonicity (Dirac, Ore, Chvatal theorems). Number of Hamiltonian cycles passing through a given edge in a graph with all degrees odd (Smith and Thomason theorems). Chvatal-Erdos theorem on Hamilton connectedness.

NOV 10, 2025 recitations

NOV 24, 2025
Orthogonal Latin Squares and Finite Projective Planes
Definition of orthogonality of Latin squares, there are at most n-1 mutually orthogonal Latin squares of order n. Definition of finite projective plane, the order of a plane, existence of finite projective planes of prime orders. Theorem: A finite projective plane of order m exists if and only if there are m-1 mutually ortogonal Latin squares of order m.

NOV 24, 2025 recitations

DEC 1, 2025
9:00 - 10:30 and 10:40 - 12:10 will be recitations (problem solving of the in-class problems). A few more in-class problems are
here .

DEC 8, 2025
9:00 - 10:30 and 10:40 - 12:10 will be two lectures (and no recitations).
Orthogonal Arrays and Balanced Incomplete Block Designs
Mutually orthogonal Latin squares as orthogonal arrays. Theorem: MOLS(n) > 1 if n>2 is odd or divisible by 4. Theorem: There are infinitely many values n congruent to 2 mod 4 such that MOLS(n) > 1.
Definition of (v,k,lambda)-BIBD. Fisher inequality.
Symmetric Block Designs
Dual design, dual projective plane. Bruck-Ryser-Chowla theorem (necessary conditions for the existence of symmetric block designs). Nonexistence of finite projective plane of order 6.

DEC 8, 2025 no recitations, but new problems and homwork IV

DEC 15, 2025
Symmetric Block Designs
Finishing the proof of Bruck-Ryser-Chowla theorem.
Steiner Triple Systems and Hadamard matrices
Equivalent definition via commutative idempotent quasigroups. Existence of Steiner triple systems (necessary and sufficient divisibility conditions).
Hadamard matrices
Equivalence to symmetric block desings of certain parameters. The order of HM is divisible by 4, construction of HM of order power of 2, Payley's construction for order a prime congruent 3 mod 4.

DEC 15, 2025 recitations - no new problems

JAN 5, 2026
Abueida-Pike theorem The block intersection graph of a BIBD is cycle-extendable (and hence Hamiltonian).

JAN 5, 2026 recitations - hints to some of the unsolved problems

Problems solved so far during the recitations
Problem 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Date solved 10/6 10/6 10/6 10/20 10/6 10/27 10/27 01/05 10/13 10/13 11/10 10/13 11/3 12/15 10/13 11/24 11/24 10/20
Problem 31 32 33 34 35 36 37 38 39 40 41 42 43 44
Date solved 11/10 12/15 12/01 11/24 12/01

Home assignment scores

Nick 1.1 1.2 1.3 2.1 2.2 2.3 3.1 3.2 3.3 4.1 4.2 4.3 Total
Vivien 1 1 1 1 1 1 1 0.9 7.9
Khorne 1 1 1 1 1 1 6
mrakomor 1 0.5 1 0.8 1 0.9 1 6.2
prezdivka 1 1 1 1 1 1 6
BeBe 1 1 1 1 1 0.1 5.1
Vojta 1 1 1 1 0.9 0.5 5.4
Natsume 0.99 0.8 1 0.9 1 1 5.69
cirka obecna 0.8 0.5 0.5 0.7 1 1 4.5
juno 1 1 1 1 1 5
hrnek 0.99 1 0.8 1 1 4.79
6 0.99 0.5 1 0.8 1 1 5.29
FEVEN 1 0.5 1 0.6 1 0.9 0 0.5 1 6.5