Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

Linear Algebra Applications in Combinatorics - NDMI028

Title:	Aplikace lineární algebry v kombinatorice
Guaranteed by:	Department of Applied Mathematics (32-KAM)
Faculty:	Faculty of Mathematics and Physics
Actual:	from 2016 to 2016
Semester:	winter
E-Credits:	6
Hours per week, examination:	winter s.:2/2, C+Ex [HT]
Capacity:	unlimited
Min. number of students:	unlimited
4EU+:	no
Virtual mobility / capacity:	no
State of the course:	taught
Language:	Czech, English
Teaching methods:	full-time
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
Is incompatible with:	NDMI023

Opinion survey results Examination dates Schedule Noticeboard

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.

Literature - Czech

Last update: T_KAM (20.04.2007)

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

Sloane, McWilliams: Coding theory

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.

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.

Construction of Golay codes.