Title: Designs, Nibbles, and Approximate Structures
Speaker: Eion Mulrenin
Date/Time/Location: Friday, February 10th, at 1:00pm, CMC 109
Abstract: For integers $1 < t < k < n$ and a positive integer $\lambda$, a family $F$ of $k$-subsets (sets of size $k$) of {$1,…,n$} is called a $t-(n,k,\lambda)$ design provided that every $t$-subset of {$1,…,n$} is contained in precisely $\lambda$ sets in the family $F$. A simple double counting argument gives necessary divisibility conditions for the existence of $t-(n,k,\lambda)$ designs, and it was asked c. 1850 (the so-called “existence conjecture”) whether these were also sufficient. In 1963, P. Erdos and H. Hanani conjectured the asymptotic existence of “approximate designs” for $\lambda=1$ and $k$ and $t$ fixed. The conjecture was verified in 1985 by V. Rodl, and in his solution, he introduced his seminal “nibble” technique, which has since become a powerful tool in extremal combinatorics. The existence conjecture was ultimately verified in 2014 by P. Keevash and in 2016 by D. Kuhn et al., with both proofs making copious use of nibble techniques. In this talk, we will introduce and prove some basic facts about combinatorial designs and sketch a proof of the Erdos-Hanani conjecture using nibble methods.