Department of

November 2020 December 2020 January 2021 Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa 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 14 15 16 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.