Department of

November 2020 December 2020January 2021Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We ThFrSa 1 2 3 4 5 6 7 1 2 3 4 5 1 2 8 9 10 11 12 13 14 6 7 8 9 10 11 12 3 4 5 6 7 8 9 15 16 17 18 19 20 21 13 14 15 16 17 18 19 10 11 12 13 141516 22 23 24 25 26 27 28 20 21 22 23 24 25 26 17 18 19 20 21 22 23 29 30 27 28 29 30 31 24 25 26 27 28 29 30 31

Tuesday, December 8, 2020

**Abstract:** A cornerstone result of extremal combinatorics due to Sauer and Shelah bounds the size of a family in terms of its VC-dimension. In this talk we will make progress towards establishing a dual version of the Sauer-Shelah lemma, where the roles of points and sets are reversed. This is equivalent to asking how many sets can we take without creating a $k$-Venn diagram, i.e. $k$ sets with all $2^k$ regions of the form $B_1 \cap B_2 \cap ... \cap B_k$, where $B_i \in \{A_i , [n] - A_i\}$, are non-empty. We will solve the first interesting case by showing that a family without a $3$-Venn has size at most $O(n^3)$.

This is joint work with Peter Keevash, Imre Leader, and Jason Long.

For Zoom information, please contact Sean at SEnglish (at) illinois (dot) edu.