NDMI028 Applications of Linear Algebra in Combionatorics - 2026/27

Monday 15:40 - K6

Recitations Monday 17:20 - K6

Requirements for "zapocet": Active participation at at least 2/3 of recitation sessions. Missed sessions can be replaced by extra homework - 1.5 problems per session - out of the following problems:
13, 15, 18, 20, 22, 24, 27, 29, 30, 32, 35, 36. Send your solutions in pdf by email to honza@kam.mff.cuni.cz.

OCT 5, 2026
Warm-up
Matrix description of graphs and set systems. Counting the number of walks between vertices of a graph via powers of its adjacency matrix. Counting the number of spanning trees of a graph via the determinant of its Laplace matrix.

OCT 5, 2026 recitations

OCT 12, 2026
Linear dependence and independence of vectors
Bounds on sizes of set systems with certain restrictions on the sizes of their intersections - almost disjoint set systems, Even-Odd-tons.
Upper bound on the size of a 2-distance point set in the n-dimensional Euclidean spaces.

OCT 12, 2026 recitations

OCT 19, 2026
Inner product of vectors, orthogonal complements
Properties and dimension of orthogonal complement. Even-Even-tons.
Cycle space of a graph, the space of cuts and their mutual orthogonality. Seidel's switching. Partition of a graph into two disjoint Eulerian subgraphs.

OCT 19, 2026 recitations

OCT 26, 2026
Both 15:40-17:10 and 17:20-18:50 will be recitations
Work on solving problems from the list. The lecture time will be substituted in one of the later classes (Dec 14, 2026, or Jan 4, 2027).

Problems solved so far during the recitations

Problem	1	2	3	4	5	6	7	8	9	10	11	12	14	17	22
Date solved	10/5	10/5	10/12	10/5	10/5	10/5	10/5	10/5	10/5	10/5	10/12	10/12	10/12	10/19	10/19
Problem	31	32	33	34	35	36	37
Date solved