Introduction to Combinatorics 1000-1M19WDK
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).
Type of course
Prerequisites (description)
Course coordinators
Learning outcomes
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 criteria
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.
Bibliography
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.
Additional information
Information on level of this course, year of study and semester when the course unit is delivered, types and amount of class hours - can be found in course structure diagrams of apropriate study programmes. This course is related to the following study programmes:
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: