##
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.
###
Grading:

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