Combinatorics and Discrete Probability Seminar
Caroline Terry
UIC
On growth of regular partitions in 3-uniform hypergraphs
Abstract: It was first observed by Alon, Fox and Zhao that VC-dimension can be used to characterize a dichotomy in the growth of regular partitions of graphs. Specifically, if a hereditary graph property H has finite VC-dimension, then results of Alon-Fischer-Newman and Lov'{a}asz-Szegedy imply all graphs is H have $\epsilon$-regular partitions of size polynomial in $1/\epsilon$. On the other hand, if H has infinite VC-dimension, then results of Gowers and Fox-Lov\'{a}sz show there are graphs in H whose smallest $\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. These dichotomies are all characterized by various analogues of VC-dimension for 3-uniform hypergraphs.
Monday October 7, 2024 at 3:00 PM in 1227 SEO