Upcoming talks
-
29 April 2024 - Youri Tamitegama (University of Oxford)
Minimal families of shattering permutations
Let $n, t, k$ be positive integers and say that a family $\mathcal{P}$ of permutations is $(k,t)$-shattering for $[n]=\set{1,\dotsc, n}$ if it induces at least $t$ distinct orders on each $k$-subset of $[n]$. In 1971, Spencer constructed $(k,k)$-shattering families of size $O(\log \log n)$ and showed that $(k,k!)$-shattering families have size $\Omega(\log n)$.
Füredi then asked in 1996 whether minimal $(k,t)$-shattering families always have sizes in one of three regimes: $O(1)$, $\Theta(\log \log n)$, $\Theta(\log n)$. In 2023, Johnson and Wickes settled the case $k=3$ affirmatively and asked whether this could be extended to general $k$. In recent joint work with António Girão and Lukas Michel show the existence of a jump between the $\Theta(\log \log n)$ regime and a new $\Theta(\sqrt{\log n})$ regime when $k\geq 4$, thereby answering both the general question of Füredi and the question of Johnson and Wickes negatively. Moreover, we settle the case $k=4$ and greatly narrow the range of $t$ for which asymptotic sizes of such families are unknown.
-
13 May 2024 - Shumin Sun (University of Warwick)
-
20 May 2024 - Camila Zárate-Guerén (University of Birmingham)