NDMI028 Applications of Linear Algebra in Combionatorics - 2024/25

Thursday 9:00 - N9

Recitations Thursday 10:40 - N9

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 3, 2024
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 3, 2024 recitations

OCT 10, 2024
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 10, 2024 recitations

OCT 17, 2024
Inner product of vectors, orthogonal complements
Properties and dimension of orthogonal complement. Even-Even-tons. Cycles 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 17, 2024 recitations

OCT 24, 2024
Linear forms and dual spaces
Linear forms, dual space, dual morphism. Seidel's switching revisited, number of nonisomorphic equivalence classes under Seidel's switching is equal to the number of nonisomorphic Eulerian graphs.

OCT 24, 2024 recitations - no new problems today

OCT 31, 2024
Shannon capacity and orthonormal representations of graphs

OCT 31, 2024 recitations

NOV 7, 2024
Eigenvectors, eigenvalues and spectra of graphs
Definitions, recap of properties (orthonormal basis consisting of eigenvectors, normal matrices, self-adjoint matrices, Frobenius theorem). Moore graphs.

NOV 7, 2024 recitations

NOV 14, 2024
Strongly regular graphs and the Friendship theorem

NOV 14, 2024 recitations

NOV 21, 2024
Interlacing of eigenvalues
The spectrum of a principal submatrix of a self-adjoint matrix interlaces its spectrum. Applications for bounds for independence and chromatic numbers of graphs.

NOV 21, 2024 recitations

DEC 5, 2024
Perfect Error-correcting Codes
Motivation, definition of perfect codes in Hamming metrics. Overview of the existence theorem. Construction of Hamming codes (1-perfect codes over alphabet whose number of symbols is a power of a prime). Sphere packing condition. Lloyd theorem (without proof). Nonexistence of nontrivial binary 2-perfect codes.

DEC 5, 2024 recitations - no new problems

DEC 12, 2024
Perfect Error-correcting Codes II
Perfect codes in distance regular graphs, Biggs theorem.

DEC 12, 2024 no recitations, no new problems

DEC 19, 2024
Perfect Error-correcting Codes III
Proof of Tietavainen theorem - there are no non-trivial t-perfect codes over an alphabet with q symbols, for q>2 and t>2.

DEC 19, 2024 recitations, no new 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/3 10/3 10/3 10/3 10/3 10/3 10/3 10/10 10/10 10/17 10/10 10/10 10/31 10/10 10/17 10/10 10/31 11/14 10/31 11/7 10/31 10/17 11/7 11/7 11/7 11/14 11/14 12/5
Problem 31 32 33 34 35 36 37
Date solved 12/19 11/14 12/5 12/19 12/5