Linear Algebra Methods in Combinatorics
MATH-672 / 2 credits
Teacher(s): Eisenbrand Friedrich, Invited lecturers (see below)
Language: English
Remark: Fall 2025. For graduate students and excellent undergraduate students. Require the basic knowledge of linear algebra and combinatorial graphs.
Frequency
Only this year
Summary
The course will provide the students the skills to use simple notions in linear algebra such as rank, dimension, vector space, eigen values, tensor product, and matrices to solve seemingly accessible problems that may be quite natural and "elementary" and yet are difficult to solve by other methods.
Content
1. Introduction to linear algebraic methods in Combinatorics with some attractive examples and puzzles.
2. Sets with restricted intersections. Frankl-Wilson theorem.
Consequences: constructive Ramsey graphs, chromatic number of $\mathbb{RYn$, counterexample to Borsuk's
conjecture. Solution of Kakeya problem in finite fields.
3. Combinatorial Nullstellensatz. Chevalley-Warning theorem. Applications to additive number
theory, combinatorics, and geometry.
4. Exterior products, Bollobl 'as theorem.
5. Shannon capacity and Lov\'asz 8-function.
6. Graph eigenvalues and their applications.
Note
Invited lecturer: Prof. Rom Pinchasi
Keywords
Linear Algebra, Combinatorics,
Learning Prerequisites
Required courses
Linear Algebra
Recommended courses
Combinatorics, Graph theorem, Combinatorial Nullstellensatz, Kakeya problem
Resources
Bibliography
L. Babai and P. Frankl, Linear Algebra Methods in Combinatorics, Department of Computer Science, University of Chicago, preliminary version, 1992
J. Matoušek, Thirty three miniatures, Mathematical and Algorithmic Applications of Linear Algebra, American Math. Society, 2010
Moodle Link
In the programs
- Number of places: 30
- Exam form: Oral (session free)
- Subject examined: Linear Algebra Methods in Combinatorics
- Courses: 12 Hour(s)
- Exercises: 12 Hour(s)
- TP: 20 Hour(s)
- Type: optional
- Number of places: 30
- Exam form: Oral (session free)
- Subject examined: Linear Algebra Methods in Combinatorics
- Courses: 12 Hour(s)
- Exercises: 12 Hour(s)
- TP: 20 Hour(s)
- Type: optional