|
|
|
||
|
Advanced course in Computer Science
Applications of linear algebraic methods in graph theory and combinatorics.
Linear dependence and independence of vectors, equiangular lines, two-distance sets, almost disjoint set systems.
Determinants.
Eigenvalues and eigenvectors, Moore graphs, strongly regular graphs.
Seidel's switching.
Error-correcting codes, namely perfect codes in Hamming metrics.
Theory of distance regular graphs and Biggs's proof of Lloyd's theorem.
Van Lint-Tietavainen's proof of nonexistence of perfect codes over finite fields.
Last update: T_KAM (20.04.2007)
|
|
||
|
Solution of home assignments is required for the credit. Last update: Kratochvíl Jan, prof. RNDr., CSc. (16.09.2020)
|
|
||
|
Cvetkovic, Doob, Sachs: Spectra of graphs Biggs: Algebraic graph theory Sloane, McWilliams: Coding theory Last update: T_KAM (20.04.2007)
|
|
||
|
The exam is oral and may be performed remotely. The knowledge and skills examined correspond to the syllabus in extent presented during the lectures. Common understanding to all notions and their relationship, theorems including proofs and ability to apply the acquired skills to simple situations related to the topics of the class are subject of the examination. Credit from the recitations must be obtained prior to enrolling to an exam. Last update: Kratochvíl Jan, prof. RNDr., CSc. (23.09.2020)
|
|
||
|
Application of linear dependence and independence - cardinality of nearly-disjoint set systems, equiangular line systems, two-distance point sets.
Set systems with prescribed parity of intersections.
Eigenvalue techniques - spectra of graphs, Moore graphs, interlacing of eigenvalues and its consequences for independence number and chromatic number of a graph.
Seidel's switching.
Perfect codes in Hamming metrics and generalization to distance-regular graphs, Biggs's proof of Lloyd theorem, van Lint-Tietavainen proof of nonexistence of perfect codes over finite fields.
Construction of Golay codes. Last update: Kratochvíl Jan, prof. RNDr., CSc. (02.10.2024)
|