Logic Seminar
Caroline Terry
UIC
Some results on the growth of regular partitions of 3-uniform hypergraphs
Abstract: Many tools have been developed in combinatorics to study global structure in finite graphs. One such tool is called Szemer'{e}di’s regularity lemma, which gives a structural decomposition for any large finite graph. Beginning with work of Alon-Fischer-Newman, Lov\'{a}sz-Szegedy, and Malliaris-Shelah, it has been shown over the last 15 years that regularity lemmas can be used to detect structural dichotomies in graphs, and that these dichotomies have deep connections to model theory. One striking example is a dichotomy in the size of regular partitions, first observed by Alon-Fox-Zhao. Specifically, if a hereditary graph property $\mathcal{H}$ has finite VC-dimension, then results of Alon-Fischer-Newman and Lovász-Szegedy imply all graphs in $\mathcal{H}$ have regular partitions of size polynomial is $1/\epsilon$. On the other hand, if $\mathcal{H}$ has infinite VC-dimension, then results of Gowers and Fox-Lov\'{a}sz show there are graphs in $\mathcal{H}$ whose smallest $1/\epsilon$-regular partition has size at least an exponential tower of height polynomial in $1/\epsilon$. In this talk, I present several analogous dichotomies in the setting of hereditary properties of 3-uniform hypergraphs.
Tuesday September 10, 2024 at 4:00 PM in 636 SEO