Coursebooks 2017-2018

Extremal Combinatorics

Tomon Istvan

English

Remarque

Next time: Spring 2018

Summary

In this course, we shall study extremal problems on finite set system. Our aim is to establish bounds on the size of families of sets satisfying certain restrictions on their sizes, intersections and containment, and discuss applications of such results in other branches of mathematics.

Content

In this course, we study extremal problems concerning collections of subsets of a finite set. This field revolves around establishing bounds on the size of families of sets satisfying certain restrictions on their sizes, intersections and containment. Many natural and fundamental questions arise in this area; many of them are still open, and some of them are answered with a variety of genuine and elegant techniques. The results discussed have applications in many different branches of mathematics as well as in computer science.

The course will cover classical results such as Sperner's lemma, the Erdos-Ko-Rado theorem and the Kruskal-Katona theorem, together with more recent results about 'concentration of measure' inequalities, applications of discrete fourier analysis and the sharp threshold phenomena of hereditary graph and hypergraph properties. Furthermore, we introduce the notion of VC dimension and present its applications in statistical learning theory, neural networks and epsilon-net theory. I will provide many open problems during the course and talk about possible future work in the area.

The following topics will be covered.

Exrtremal Set Theory:

Sperner's lemma on antichains and related results such as the LYM inequality, vertex and edge isoperimetric inequalities such as the Kruskal-Katona theorem and Harper's theorem, the Erdos-Ko-Rado theorem on uniform intersecting families.

VC-dimension:

Sauer-Shelah lemma, applications of the VC-dimension in learning algorithms, complexity and epsilon-net theory

Probability:

Harris's lemma, the Four-Functions theorem (Ahlswede-Daykin inequality),  the Kahn-Kalai-Linial theorem on maximal influence, Friedgut-Kalai Sharp Threshold Theorem.

Keywords

intersection patterns, isopermietric inequalities, concentration of measure, VC dimension

Learning Prerequisites

Required courses

The course is self contained, but familiarity with basic concepts of graph theory and probability is appreciated.

Reference week

Lecture
Exercise, TP
Project, other

legend

• Autumn semester
• Winter sessions
• Spring semester
• Summer sessions
• Lecture in French
• Lecture in English
• Lecture in German