Ideas and techniques from algebra (including linear algebra) have been used with striking success (and in surprising ways) in combinatorics, discrete geometry, and theoretical computer science, leading to many breakthroughs and solutions to various long-standing open problems.
The aim of this course is to explain some of these results and methods. The precise choice of topics will depend on the audience's background; sample topics include:
- Dimension arguments and set systems with restricted intersections: counterexamples to Borsuk's conjecture, explicit constructions of Ramsey graphs, and the chromatic number of the plane
- Polynomial methods and applications: the finite field Kakeya problem, the cap-set problem, and Erdős distance problems
- the Combinatorial Nullstellensatz and applications in additive number theory and graph coloring
- Eigenvalues of graphs, random walks, quasi-random graphs, and constructions of expander graphs
- Shannon capacity, the Lovász θ-function, and semidefinite programming relaxations
- Stanley-Reisner rings and face numbers of polytopes and triangulated spheres
Target group: Students in Mathematics and Computer Science.
Prerequisites: None
Evaluation: Regular homework assignments + active participation + final oral exam
Teaching format: None
ECTS: 3 Year: 2025
Track segment(s):
Elective
Teacher(s):
Uli Wagner
Teaching assistant(s):
- Trainer/in: Uli Wagner