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.