Combinatorics Seminar

When: Sunday, December 23, 10am
Where: Schreiber 309
Speaker: Nathan Keller, Bar-Ilan University
Title: Stability for the Complete Intersection Theorem, and the Forbidden Intersection Problem of Erdős and Sós

Abstract:

A family $F$ of sets is said to be $t$-intersecting if $|A \cap B| \geq t$ for any $A,B \in F$. The seminal Complete Intersection Theorem of Ahlswede and Khachatrian (1997) gives the maximal size $f(n,k,t)$ of a $t$-intersecting family of $k$-element subsets of $[n]=\{1,2,\ldots,n\}$, together with a characterisation of the extremal families.

The forbidden intersection problem, posed by Erdős and Sós in 1971, asks for a determination of the maximal size $g(n,k,t)$ of a family $F$ of $k$-element subsets of $[n]$ such that $|A \cap B| \neq t-1$ for any $A,B \in F$ (that is, only a single intersection size is forbidden).

In this talk we show that for any fixed $t \in \mathbb{N}$, if $2t \leq k \leq n/2-o(n)$, then $g(n,k,t)=f(n,k,t)$. This solves the Erdős-Sós problem for any constant $t$, except for in the ranges $n/2-o(n) < k < n/2+t/2$ and $k < 2t$. A central step in our proof is a stability version for the Complete Intersection Theorem, which in itself proves a conjecture of Friedgut.

Joint work with David Ellis and Noam Lifshitz.