Friday 9:00 - K10C
Recitations Friday 10:40 - K10C
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 4, 2024 recitations
OCT 11, 2024
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 11, 2024 recitations
OCT 18, 2024
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 18, 2024 recitations
OCT 25, 2024
Edmonds's algorithm for maximum matching in a general graph
OCT 25, 2024 recitations
NOV 1, 2024
Chooseability of graphs
List colorings and chooseability. Chooseability of subclasses of planar graphs.
Bounds on chooseability via orientations with kernels.
NOV 1, 2024 recitations
NOV 8, 2024
Graph Coloring and Chooseability II
Coloring graphs on surfaces of higher (orientable) genus - Heawood Theorem. Edge coloring - Vizing Theorem. Chooseability of line graphs of bipartite graphs
(i.e., edge-chooseability of bipartite graphs).
NOV 8, 2024 recitations
NOV 15, 2024
Planar graphs
Some lemmas on drawings of planar graphs. Lemma about edge-contraction in 3-connected graphs. Proof of Kuratowski theorem.
NOV 15, 2024 recitations
NOV 22, 2024
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 22, 2024 recitations
NOV 29, 2024
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 29, 2024 recitations
DEC 6, 2024
Orthogonal Arrays and Balanced Incomplete Block Designs
Mutual 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.
DEC 6, 2024 recitations
DEC 13, 2024
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 13, 2024 recitations - no new problems
DEC 20, 2024
Steiner Triple Systems and Hadamard matrices
Existence of Steiner triple systems (necessary and sufficient divisibility conditions).
Hadamard matrices - the order is divisible by 4, construction of HM of order power of 2, Payley's construction for order a prime congruent 3 mod 4.
DEC 20, 2024 recitations - no new problems
| 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/4 | 11/29 | 12/6 | 12/6 | 10/18 | 10/11 | 11/22 | 10/18 | 10/18 | 10/18 | 10/18 | 10/25 | 10/18 | 10/25 | 11/1 | 11/1 | 10/25 | 11/8 | 11/8 | 11/8 | 11/8 | |||||||||
| Problem | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | ||||||||||||||||
| Date solved | 11/15 | 12/13 | 11/14 | 12/6 | 11/22 | 11/29 | 12/20 |
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 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Zaba | 1 | 1 | 1 | 1 | 1 | 1 | 6 | ||||||
| kokostra grafu | 1 | 1 | 1 | 1 | 1 | 1 | 6 | ||||||
| Rikam_chtel-by | 1 | 1 | 1 | 1 | 4 | ||||||||
| {0,{0}} +2 | 1 | 1 | 1 | 1 | 1 | 5 | |||||||
| 11010 | 1 | 1 | 1 | 1 | 1 | 5 | |||||||
| Ctyrlistek | 1 | 1 | 1 | 0.9 | 1 | 4.9 | |||||||
| kopretina | 1 | 1 | 1 | 1 | 1 | 1 | 6 | ||||||
| Banas | 1 | 1 | 1 | 0.75 | 1 | 1 | 0 | 0 | 5.75 | ||||
| Zulu | 1 | 1 | 1 | 0.85 | 0.95 | 0 | 0.9 | 1 | 6.7 | ||||
| ancapator | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 6 |