Ideas and methods from topology have found striking applications in discrete mathematics and theoretical computer science (e.g., Lovász' solution of Kneser's conjecture in 1978). The aim of this course is to explain some of these results and methods. Sample topics incude:
- Topological lower bounds for the chromatic number of a graph
- Decision tress complexity and evasiveness of graph properties
- (Non)embeddability and Tverberg-type results
- Mass partition problems
- Impossibility theorems in distributed computing
- Matchings in hypergraphs
Target group: Students with a strong background in mathematics or theoretical computer science. We will make an effort to keep the specific prerequisites minimal and adapt the class to the background of the audience, introducing topological notions and results as we go along; the main prerequisite is mathematical maturity.
Prerequisites: None
Evaluation: Homework assignments and oral final exam.
Teaching format: Lectures and recitation.
ECTS: 3 Year: 2024
Track segment(s):
Elective
Teacher(s):
Uli Wagner
Teaching assistant(s):
Gianluca Tasinato
- Teacher: Uli Wagner
- Teaching Assistant: Gianluca Tasinato