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, 24, 29, 30, 32, 35 (more problems will be announced later).
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 14, 2024 recitations

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
Problem 31 32 33 34 35 36 37
Date solved 11/14