Combinatorics Seminar

When: Sunday, December 4, 10am
Where: Schreiber 309
Speaker: Tuan Tran, Czech Academy of Sciences
Title: Erdős-Ko-Rado: structure and supersaturation

Abstract:

The study of intersecting families is central to extremal set theory, starting with the Erdős-Ko-Rado theorem of 1961. This theorem asserts that when n≥2k, the largest k-uniform intersecting set family over [n] has size \binom{n-1}{k-1}, and that when n>2k, the only such families are trivial.

One particularly important extension of the theorem is that of stability: to show that large intersecting families must be close to trivial in their structure.

In this talk I will present a removal lemma for intersecting families, which extends the stability results beyond the intersecting setting. In particular, we show that large families with relatively few disjoint pairs must be close to trivial in structure. We shall then demonstrate an application of this result, determining the minimum number of disjoint pairs in small k-uniform families for k=o(\sqrt{n}), and thus extending a result of Das, Gan and Sudakov.

The talk is based on my joint works with Das, and with Balogh, Das, Liu and Sharifzadeh.