Algebraic methods in combinatorics

MATH-526 / 5 credits

Teacher: Janzer Oliver

Language: English

Summary

In this course we study how algebraic methods can be used to solve problems in combinatorics. The main tools used are from linear algebra and from the theory of polynomials.

Content

We will present the following important algebraic tools in combinatorics:

  • linear algebraic methods
  • spectral graph theory
  • Chevalley-Warning theorem
  • Combinatorial Nullstellensatz

Several famous applications of these methods will be discussed, such as:

  • Oddtown problem
  • finite field Kakeya problem
  • set systems with restricted intersections
  • explicit constructions of Ramsey graphs
  • the Sensitivity conjecture
  • the cap-set problem

 

Learning Prerequisites

Required courses

An introductory linear algebra course

Recommended courses

Graph theory (MATH-360)

Important concepts to start the course

Familiarity with basic concepts of linear algebra, finite fields and polynomials are essential for this course. In particular, the student should be comfortable with the following notions from these subjects:

  • finite fields
  • vector spaces
  • matrices
  • linear independence
  • dimension
  • inner product
  • orthogonal complement
  • eigenvalues
  • eigenvectors

The first exercise class will be devoted to recalling the necessary background in linear algebra.

Teaching methods

In-person lectures + in-person exercise classes covering weekly exercise sheets.

Expected student activities

The students are expected to attend the lectures and the exercise classes. In addition, they are expected to attempt the problems on the exercise sheets and to submit their solutions of a selected subset of the exercises for grading.

Assessment methods

Written final exam

Supervision

Office hours No
Assistants Yes
Forum Yes

Resources

Bibliography

L. Babai and P. Frankl: Linear Algebra Methods in Combinatorics, preliminary version, 1992

Ressources en bibliothèque

Notes/Handbook

Lecture notes will be provided.

Moodle Link

In the programs

  • Semester: Spring
  • Exam form: Written (summer session)
  • Subject examined: Algebraic methods in combinatorics
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: optional
  • Semester: Spring
  • Exam form: Written (summer session)
  • Subject examined: Algebraic methods in combinatorics
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: optional
  • Semester: Spring
  • Exam form: Written (summer session)
  • Subject examined: Algebraic methods in combinatorics
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: optional

Reference week

Related courses

Results from graphsearch.epfl.ch.