SubjectsSubjects(version: 845)
Course, academic year 2018/2019
   Login via CAS
Linear Algebra Applications in Combinatorics - NDMI028
Title in English: Aplikace lineární algebry v kombinatorice
Guaranteed by: Department of Applied Mathematics (32-KAM)
Faculty: Faculty of Mathematics and Physics
Actual: from 2018 to 2018
Semester: winter
E-Credits: 6
Hours per week, examination: winter s.:2/2 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Guarantor: prof. RNDr. Jan Kratochvíl, CSc.
Class: Informatika Mgr. - Diskrétní modely a algoritmy
M Mgr. MSTR
M Mgr. MSTR > Povinně volitelné
Classification: Informatics > Discrete Mathematics
Annotation -
Last update: T_KAM (20.04.2007)
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.
Course completion requirements -
Last update: prof. RNDr. Jan Kratochvíl, CSc. (18.10.2018)

Attendance at exercise classes is required, at most three can be missed. In case of more than three missed exercise classes, solution of some homework problems may be required for the credit. There is no second try.

Literature - Czech
Last update: T_KAM (20.04.2007)

Cvetkovic, Doob, Sachs: Spectra of graphs Biggs: Algebraic graph theory

Sloane, McWilliams: Coding theory

Requirements to the exam -
Last update: prof. RNDr. Jan Kratochvíl, CSc. (18.10.2018)

The exam is oral. 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.

Syllabus -
Last update: prof. RNDr. Jan Kratochvíl, CSc. (18.10.2018)

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, interlacing of eigenvalues, Moore graphs.

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.

Seidel's switching.

Construction of Golay codes.

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html