Teacher: Rom Pinchasi
TA: Neta Singer
Credits: 2
Duration: 6 weeks
Language: English
Time and Place:
- Tuesdays 9.9 / 16.9 / 23.9 / 30.9 / 7.10 / 14.10 from 13h15 to 15h in room ELD 120
- Thursdays 11.9 / 18.9 / 25.9 / 2.10 / 9.10 / 16.10 from 11:15 to 13:00 in room CM 1 221
Requirements: For graduate students and excellent undergraduate students. Requires basic knowledge of linear algebra and combinatorial graphs.
Summary
The course will spread over 6 weeks, where every week will include two hours of lecture and two hours of recitation.
We will start by exploring variety of beautiful examples of natural combinatorial problems and puzzles with surprising solutions using linear algebra. We will then present the method of Combinatorial Nullstellensatz invented by Noga Alon with various fun and beautiful applications to Combinatorics and Number Theory. We will present the Kakeya problem and its solution over finite fields by Zeev Dvir. The beautiful counterexample to Borsuk’s conjecture found by Jeff Khan and Gil Kalai will be discussed and explored. We will talk about the importance of eigenvalues to graph theory and present some fun examples.
In the recitations the participants will present solutions and extensions to selected problems that will be advertised weekly in connection with the material discussed during lectures. We will use the time to consider original variations of some of the problems and suggest together ways of tackling them, hopefully solving some and leaving the others for further research and even more fun.
Tentative schedule
- Week 1: Introduction with some attractive Combinatorial examples and puzzles whose solutions combine Linear Algebra methods.
- Week 2: Combinatorial Nullstellensatz with applications to number theory, combinatorics, and geometry.
- Week 3: Counterexample to Borsuk’s Conjecture and related results.
- Week 4: Kakeya problem and its solution over finite fields.
- Week 5: Set systems with intersection constraints, Bollobas Theorem and exterior products.
- Week 6: More fun with eigenvalues, vectors, and matrices.