Wednesday 9:00 - K8
Recitations Friday 14:00 - K2
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.
OCT 6, 2023 recitations
OCT 11, 2023
Hall 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).
OCT 13, 2023 recitations
OCT 18, 2023
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.
OCT 20, 2023 recitations
OCT 25, 2023
Edmonds's algorithm for maximum matching in a general graph
(Lecture given by Pavel Valtr.)
OCT 27, 2023 recitations
NOV 1, 2023
Chooseability
Definition of list coloring and chooseability. Relation to d-degenerate graphs. Planar graphs are 5-chooseable (Thomassen), but not all planar graphs are 4-chooseable (Voigt). Bounding chooseability via orientations with kernels.
NOV 3, 2023 recitations
NOV 8, 2023
Coloring gaphs embeddable in surfaces of higher genus, edge-colorings of graphs.
Surfaces of genus g. Euler formula, degeneracy. Heawood theorem. Vizing theorem on edge colorings.
NOV 10, 2023 recitations
NOV 15, 2023
Kuratowski theorem on planar graphs.
Some lemmas on drawings of planar graphs. Lemma about edge-contraction in 3-connected graphs. Proof of Kuratowski theorem.
NOV 22, 2023
Hamiltonian graphs.
Hamiltonian cycles and Hamiltonian paths in graphs. Sufficient conditions for existence of a Hamiltonian cycle (the theorems of Dirac, Ore and Chvatal).
Parity of the number of Hamiltonian cycles passing through a given edge
(the theorems of Smith and Thomason).
Chvatal-Erdos theorem on Hamiltonian connectedness of a graph
(if the vertex-connectivity is strictly bigger than the independence number).
NOV 24, 2023 recitations
NOV 29, 2023
Latin squares and finite projective planes.
Orthogonal Latin squares. Finite projective plane - definition, all lines have the same number of points, an FPP of order n exists if and only if there exist n-1 mutually orthognal Latin squares of order n. An FPP(n) exists if n is a power of a prime.
DEC 1, 2023 recitations - no new problems this time.
DEC 6, 2023
Orthogonal Latin squares as Orthogonal Arrays. Balanced Incomplete Block Designs.
Definition of orthogonal arrays, construction by tensor product. Corollary that for n odd or divisible by 4, there are at least 2 orthogonal Latin squares of order n.
Theorem that for every n=12k+10, there are at least 2 orthogonal Latin squares of order n.
Definition of (v,k,lambda)-BIBD, divisibility conditions for existence of (v,k,lambda)-BIBD for parameters v,k,lambda.
DEC 8, 2023 recitations - no new problems this time.
DEC 13, 2023 - class cancelled due to positive covid test
DEC 15, 2023 recitations
DEC 20, 2023
Symmetric block designs
Home assignment scores
| Nick | 1.1 | 1.2 | 1.3 | 2.1 | 2.2 | 2.3 | 3.1 | 3.2 | 3.3 | Total |
|---|---|---|---|---|---|---|---|---|---|---|
| Efoxy | 1 | 1 | 3 | 1 | 1 | 1 | 8 | |||
| Filip(1+i) | 1 | 1 | 3 | 0.95 | 1 | 1 | 1 | 1 | 1 | 10.95 |
| DPK | 1 | 0.9 | 3 | 0.5 | 0.8 | 1 | 7.2 | |||
| Hvozdik | 1 | 0.5 | 2 | 0.5 | 1 | 1 | 6 | |||
| zirafa | 0.9 | 1 | 1.5 | 1 | 1 | 1 | 6.4 | |||
| buffer | 0.8 | 1 | 0.67 | 2.47 | ||||||
| Hall | 0.95 | 1 | 1.1 | 1 | 1 | 5.05 | ||||
| 32591 | 1 | 0.75 | 1.83 | 1 | 1 | 1 | 6.58 | |||
| Riadok | 1 | 0.9 | 1 | 1 | 1 | 1 | 1 | 6.9 | ||
| Brambora | 0.9 | 1 | 1.9 |
There will be 4 sets of 3 problems each, assigned on Oct 13 (due date Nov 13), Nov 3 (due date Nov 27), Nov 24 (due date Dec 18) and Dec 15 (due date Jan 8). Each problem can earn you 1 point, with a few exceptions (for problem 1.3, you can get 3 points, and for problem 4.3 you can earn 2 points - 1 point for 4.3.a and 1 point for 4.3.b).
For attending the recitation classes, there will be 12 classes counted (on Dec 22 there is no recitation class, but an exam "predtermin", and the last one on Jan 12, 2024, will be a re-cap session).