BIMSA >
Research seminar in Discrete Mathematics
Research seminar in Discrete Mathematics
Beyond Sauer–Shelah for highly structured set systems
Beyond Sauer–Shelah for highly structured set systems
Organizers
Jie Ma
, Benjamin Sudakov
Speaker
Rose McCarty
Time
Tuesday, May 26, 2026 5:05 PM - 6:15 PM
Venue
Online
Online
Zoom 787 662 9899
(BIMSA)
Abstract
The Sauer–Shelah lemma is a fundamental tool in the combinatorics of set systems. It says that if an $n$-element set system does not contain $d$ elements on which all $2^d$ possible intersections occur, then it has at most $n^d$ sets. For certain highly structured set systems, this bound can be improved to linear or almost linear in $n$. We discuss two examples.
First, we prove that the bound is $n^{1+o(1)}$ for set systems from monadically dependent graph classes. These are the classes which are well-structured from the perspective of model-theory.
Second, we reinterpret the Matroid Growth Rate Theorem as giving a bound of $\mathcal{O}(n)$ for certain set systems. This new perspective yields a short proof that a theorem of Thomassen from 1984 generalizes from graphs to representable matroids.
First, we prove that the bound is $n^{1+o(1)}$ for set systems from monadically dependent graph classes. These are the classes which are well-structured from the perspective of model-theory.
Second, we reinterpret the Matroid Growth Rate Theorem as giving a bound of $\mathcal{O}(n)$ for certain set systems. This new perspective yields a short proof that a theorem of Thomassen from 1984 generalizes from graphs to representable matroids.