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.
Speaker Intro
Rose McCarty is an Assistant Professor in math and computer science at Georgia Tech. She did postdocs at Warsaw and Princeton. She received her PhD in Combinatorics and Optimization from the University of Waterloo in 2022. Rose's research is in structural graph theory and its applications and connections to other areas.