Discrete Mathematics (Spring 2018)

Supervisor: Wojciech Samotij
e-mail: samotij(at)post.tau.ac.il
Course #: 0366-3407-01
Wednesday, 16:10–18:00
Schreiber 209
School of Mathematical Scienes
Tel Aviv University

Course description

In this seminar, the participants will present a variety of classical results in the (widely understood) area of discrete mathematics (graph theory, additive number theory, discrete geometry, etc.) that have short elegant proofs. Among other sources, the topics will be selected from the books "The Art of Mathematics: Coffee Time in Memphis" by Bollobás, "Proofs from THE BOOK" by Aigner and Ziegler, and "Thirty-three Miniatures" by Matoušek

The seminar has no prerequisites, but it will be conducted in English.

Textbooks

B. Bollobás, The Art of Mathematics: Coffee Time in Memphis, Cambridge University Press, 2006
M. Aigner, G. Ziegler, Proofs from THE BOOK, 5th edition, Springer, 2014
J. Matoušek, Thirty-three Miniatures. Mathematical and Algorithmic Applications of Linear Algebra, American Mathematical Society, 2010

Schedule

March 7
Introduction; presentation of topics
March 14
Counting perfect matchings in planar graphs
March 21
Crossing lemma and its applications
March 26
Shuffling cards
April 11
Three theorems in convex geometry
April 25
Bootstrap percolation in the integer grid
May 2
Sperner's theorem and the Littlewood–Offord lemma
May 9
Three lemmas in additive combinatorics
May 16
Shannon capacity of C5
May 23
Borsuk's conjecture
May 30
The Erdős–Ko–Rado theorem and the chromatic number of the Kneser graph
Jyne 6
Upper bounds on permanents via entropy
June 13
The Kakeya problem over finite fields