When: Sunday, June 13,
10am
Where: Schreiber 309
Speaker: Benny Sudakov,
ETH Zurich
Title: Small doubling,
atomic structure and l-divisible set families
A central theme in additive combinatorics is the study of the structure of sets with small doubling, i.e. sets $A$ such that $A + A$ has size not much larger than $A$. In this talk we discuss a problem of a similar flavor for set systems.
Given a set-family $F$, let $F*F=\{A \cap B:A,B\in F\}$. We measure the size of $F$ by the dimension of the subspace spanned by the characteristic vectors of the sets in $F$ over some field. What can we say about $F$ if $F*F$ is not much larger than $F$? Observe that if $S$ is an atomic set-family, i.e., the ground set is split into disjoint subsets and $S$ contains their arbitrary unions, then $S* S = S$. Our structure theorem shows that this is essentially the only possible example: any set-family $F$ with small `doubling' must be close to being atomic. We will use this theorem to solve a 40 year old problem of Frankl and Odlyzko on set families with restricted intersections.
Joint work with L. Gishboliner and I. Tomon