Algebraic Methods in Combinatorics

Ideas and techniques from algebra (including linear algebra) have been used with striking success (and sometimes in surprising ways) in combinatorics, discrete geometry, and theoretical computer science, leading to breakthroughs and solution's 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; possible examples of 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 application: the finite field Kakeya problem, the joints 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 θ-funcDon, and semidefinite programming relaxaDons- Stanley-Reisner rings and face numbers of polytopes and triangulated spheres

Target group: Students with a solid background in mathematics and/or theoretical computer science

Prerequisites: We will assume that the students are familiar with linear algebra; beyond that, we will keep the specific prerequisites minimal and aim to adapt to the background of the audience, introducing more advanced algebraic notions and results as we go along; the main prerequisite is mathematical maturity.

Evaluation: graded homework + class participation + exam

Teaching format: lecture + recitation

ECTS: 3 Year: 2020

Track segment(s):
CS-ALG Computer Science - Algorithms and Complexity
MAT-ALG Mathematics - Algebra
MAT-DISC Mathematics - Discrete Mathematics
MAT-GEO Mathematics - Geometry and Topology

Teacher(s):
Vojtech Kaluza Uli Wagner

Teaching assistant(s):

If you want to enroll to this course, please click: REGISTER