Introduction to Combinatorics

elective monographs

it is assumed that the students are familiar with basic concepts of linear algebra (Linear algebra and Geometry I) and mathematical analysis (Mathematical Analysis I.1)

The course will cover several basic topics studied in combinatorics. This includes classical counting techniques and combinatorial structures, combinatorics of points and convex sets in R^n, extremal combinatorics, the probabilistic method and its applications to graph theory and number theory, elements of graph theory, algebraic method, and analysis on the discrete cube. We shall focus on interactions between different fields of mathematics. In particular, we shall show how various probabilistic, analytic and algebraic methods can be used to study combinatorial objects.

We plan to cover the following topics:

I. Enumerative combinatorics: generating functions and linear recurrences, Fibonacci, Bell and Stirling numbers and their properties, Catalan structures ( triangulations of polygons, Dyck paths, non-crossing partitions, 123 pattern avoiding permutations), reflection principle, Burnside's lemma, Young tableau and Hook length formula.

II. Geometric combinatorics: Helly, Radon and Carathéodory theorems, two distance problem, Kahn-Kalai counterexample to Borsuk's conjecture, moment curve and cyclic polytopes, Szemerédi–Trotter theorem, Bangs solution to Tarski's plank problem, Equiangular lines in R^n, Welch bound.

III. Extremal combinatorics: Erdős-Ko-Rado theorem, Sperner's theorem and LYM inequality, Dilworth's and Mirsky's theorems, Littlewood–Offord problem, Sauer–Shelah lemma and Vapnik–Chervonenkis dimension, Fisher's inequality on block designs, Ramsey numbers, Erdős–Szekeres theorem.

IV. The probabilistic method: first moment and second moment method with applications, Lovasz Local Lemma, Erdős-Renyi random graph and examples of sharp thresholds phenomenon.

V. Elements of graph theory: Eulerian graphs and Hamiltonian graphs, planar graphs, Euler's formula, Cayley's formula, chromatic number of a graph, Five color theorem, directed graphs, tournaments, Menger's theorem, Hall's theorem, max-flow min-cut theorem, elements of spectral graph theory, Kirchhoff's matrix tree theorem, ekspanders and their basic properties, matroids (basic concepts).

VI. Algebraic methods in combinatorics: Combinatorial Nullstellensatz, Cauchy-Davenport inequality, Erdős-Ginzburg-Ziv theorem, Proof of the finite field Kakeya conjecture, Graham Pollak Theorem.

VII. Boolean functions and the discrete hypercube: Walsh functions and spectral analysis on the discrete cube, proof of Condorcet theorem (social choice), Harper's isoperimetric inequality, Khintchine inequality, Huang's proof of sensitivity conjecture, Hypercontractivity and Kahn–Kalai–Linial theorem.

VIII. Other topics: Thue sequence avoiding repetitions, topological methods in combinatorics (proof of Kneser’s conjecture), elements of additive combinatorics (proof of Roth's theorem on 3-term arithmetic progressions), singularity of random Bernoulli matrices, Komlos conjecture, Brunn-Minkowski inequality and isoperimetric inequality, elements of cryptography (Miller-Rabin test, RSA system).

1. N. Alon, J. H. Spencer, The probabilistic method (2ed), New York: Wiley-Interscience, 2000.

2. R. O'Donnell, Analysis of Boolean functions, Cambridge University Press, New York, 2014.

3. J. Matoušek, Lectures on discrete geometry, Graduate Texts in Mathematics, 212. Springer-Verlag, New York, 2002.

4. N. Alon, Combinatorial nullstellensatz, Combinatorics, Probability and Computing 8, 1999.

5. T. Tao, V. Vu, Additive combinatorics, Cambridge Stud. Adv. Math., vol. 105, Cambridge Univ. Press, Cambridge, 2006.

6. I. Pak, Lectures on Discrete and Polyhedral Geometry, https://www.math.ucla.edu/~pak/book.htm

7. B. Bollobás, Set systems, hypergraphs, families of vectors and combinatorial probability, Cambridge University Press, Cambridge, 1986.

Students

1. Know basic combinatorial objects such as set partitions and various Catalan structures.

2. Know how to use basic counting techniques.

3. Know basic combinatorial properties of convex sets in Euclidean spaces.

4. Are familiar with combinatorics of finite sets in Euclidean spaces (i.e. with problems related to distances and scalar products).

5. Know basic theorems in extremal combinatorics.

6. Know how to use the probabilistic method.

7. Are familiar with basic concept of graph theory

8. Know examples of the use of algebraic techniques in combinatorics

9. Are familiar with analysis on the discrete cube

10. Know examples of theorems in additive combinatorics

assessment methods and assessment criteria: final grades will take into account homework grades, two midterm exams, final written exam and oral exam (for selected students). assessment criteria will be different for students of different stages.