Beyond Sauer–Shelah for highly structured set systems
组织者
马杰
, 本杰明·苏达科夫
演讲者
Rose McCarty
时间
2026年05月26日 17:05 至 18:15
地点
Online
线上
Zoom 787 662 9899
(BIMSA)
摘要
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.
演讲者介绍
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.