Extremal Combinatorics

Sep 4, 2024 — Dec 4, 2024

About the course

This course covers classical problems and modern techniques in extremal combinatorics. The first part of the course is on extremal properties of families of sets: e.g.

• What is the largest size of a collection of k-element subsets of a set of size n in which any two sets in the collection intersect?
• What is the largest size of a collection of subsets of a set of size n in which no set is properly contained within another?

Other topics may include VC dimension, Kneser’s Conjecture, the Kruskal-Katona Theorem and the Littlewood Offord Problem. The rest of the course is on extremal graph theory: e.g.

• What is the maximum number of edges in a triangle-free graph on n vertices?
• What is the minimum number of 6-cycles in a graph with n vertices and m edges?
• What is the minimum size of an independent set in a triangle-free graph?

Other topics may include the Szemerédi Regularity Lemma, Shannon Capacity, the Entropy Method, the Container Method and Stability. The course webpage, which includes a link to a preliminary version of the course notes, can be found here.

Registration

This course is available for registration under the Western Dean's Agreement. To register, you must obtain the approval of the course instructor and you must complete the Western Dean's agreement form , using the details below. The completed form should be signed by your home institution department and school of graduate studies, then returned to the host institution of the course.

Other Course Details