Extremal Combinatorics, Spring 2026

What:

When setting the derivative to zero does not work, there is extremal combinatorics. It is a medley of techniques that are used to find discrete structures that maximize whatever quantity we care about.

Though we will occasionally discuss specific small examples and constructions, we will primarily focus on large-scale behavior and asymptotics.

This an advanced graduate course in combinatorics. This means that, in addition to being familiar with combinatorics at the basic graduate level, the students must be fluent in undergraduate mathematics, such as algebra and analysis.

The emphasis will be on the techniques. The goal is to learn a variety of ways of attacking extremal problems involving discrete objects. Some results will therefore be discussed more than once from different viewpoints. The main areas covered include:

• Extremal graph theory: Theorems of Tur\'an and Ramsey. Bipartite Tur\'an problems, and related constructions. Elements of finite geometry.
• Szemerédi's Regularity Lemma: Statement, proof, variations. Numerous applications.
• Extremal set theory: Sperner's theorem about antichains. Intersecting families. Sunflowers. Applications of linear algebra.

Office hours:

By appointment.

Course activities:

• There there will be several homeworks. Students will submit the solutions via e-mail, and then be asked to present their solutions in class.
• There will be a single oral exam (before mid-semester break).
• Students will take turns scribing lecture notes.
• In lieu of the final exam, each student read and present a paper on extremal combinatorics. List of suggested papers will be circulated before the mid-semester break.

The course grades will be determined by homework solutions (5%), homework presentations (15%), scribing (20%), exam (25%), and the final presentation (35%).

Homework is primarily meant for practice, not assessment. To make the most of this practice, students are encouraged to work significant amount of time independently.

Use of external resources (both animate and inanimate) on homework is permitted, but must always be fully disclosed and cited. Failure to do so is an academic integrity violation, and can result in failing the class. No external resources may be used on the exams.

Homework must be submitted in LaTeX via e-mail. I want both the LaTeX file and the PDF that is produced from it. The filenames must be of the form andrewid_extremal_homeworknumber.tex and andrewid_extremal_homeworknumber.pdf respectively. Pictures and commutative diagrams do not have to be typeset; a legible photograph of a hand-drawn picture is acceptable. The homework must be submitted by 10:00pm of the day it is due. For each 5 minutes past the deadline, the assignment grade is reduced by 10%.

Staying sane and healthy:

This is a graduate course. It is designed to challenge your brain with new and exciting mathematics, not to wear your body down with sleepless nights. Start assignments early, and get good nutrition and exercise. Pace yourself, for semester is long. If you find yourself falling behind or constantly tired, talk to me.

Lectures:

• January 12: Class overview. Turán's theorem (rough and precise).
• January 14: Turán's theorem (second proof). Turán density. Supersaturation.
• January 16: Kővári–Sós–Turán theorem. Unit distances. The hypergraph generalization of Kővári–Sós–Turán theorem. Homework #1