Topics in Combinatorics - Extremal Combinatorics (MAT577 and MAT478)

Noga Alon (first name initial followed by last name at math dot princeton dot edu)
Spring 2022-2023, Tuesday and Thursday 9:30-10:50

The webpage of the course in Canvas:

Extremal Combinatorics

Procedural Matters:

Prerequisites: Basic knowledge of Discrete Mathematics, Linear Algebra and Probability.

Sample Reading List:
Much of the topics covered in the course appear in the books and papers listed below. Other topics appear in recent papers, to be mentioned during the term.
N. Alon, Combinatorial Nullstellensatz, Combinatorics, Probability and Computing 8 (1999), 7-29.
N. Alon and J. H. Spencer, The Probabilistic Method, Fourth Edition, Wiley, 2016, Chapters 9.4 and 17.
J. Balogh, R. Morris and W. Samotij, Independent sets in hypergraphs. J. Amer. Math. Soc. 28 (2015), no. 3, 669–709.
J. Ellenberg and D. Gijswijt, On large subsets of F_n^q with no three-term arithmetic progression. Ann. of Math. (2) 185 (2017), no. 1, 339–343.
O. Goldreich, Introduction to Property Testing, Cambridge University Press, 2017, Chapter 8.
L. Lovasz, On the Shannon capacity of a graph, IEEE Transactions on Information Theory IT-25, (1979), 1-7.
D. Saxton and A. Thomason, Hypergraph containers, Invent. Math. 201 (2015), 925–992.

Course syllabus:

Extremal Combinatorics deals with the problem of determining or estimating the maximum or minimum possible cardinality of a collection of finite objects that satisfies certain requirements, as well as with the investigation of inequalities between combinatorial invariants, and questions dealing with relations among them. The subject is often motivated by questions in other areas including Computer Science, Information Theory, Number Theory and Geometry. The topics that will be covered in the course include Graph powers, the Shannon capacity and the Witsenhausen rate of graphs, Szemeredi's Regularity Lemma and its applications in graph property testing and in the study of sets with no 3 term arithmetic progressions, the Combinatorial Nullstellensatz and its applications, the capset problem and related topics as time permits.


For undergrads who need to receive a grade, there will be a few problem sets over the semester.