[Theory] Logic seminar October 10

[Maryanthe Malliaris via Theory]

Dear all,

Caroline Terry's talk in the logic seminar tomorrow, "On the growth of regular partitions in 3-uniform hypergraphs" (see below) may be of interest to people on this list.

MM


-------------------------------------

Logic Seminar

Speaker: Caroline Terry (UIC)

Location: Eckhart 206, 5-6pm

Title: On the growth of regular partitions in 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 H has finite VC-dimension, then results of Alon-Fischer-Newman and Lovász-Szegedy imply all graphs in H have regular partitions of size polynomial in $\eplsilon^{-1}$. 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 have size an exponential tower of height polynomial in $\epsilon^{-1}$. In this talk, I present several analogous dichotomies in the setting of hereditary properties of 3-uniform hypergraphs.



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20241010/cae6c111/attachment-0001.html>