Model Theory Seminar
Roland Walker
UIC
Definable Regularity for NIP Relations, Part II
Abstract: The Szemerédi Regularity Lemma (1976) has proven to be a very important tool in extremal graph theory with many applications to number theory and computer science as well. It basically says that the vertices of any finite graph can be partitioned in such a way that the edges between any pair of sets from the partition are uniformly (or randomly) distributed up to a requested nonzero margin of error $\varepsilon$. Furthermore, the size of partition needed to obtain such regularity depends only on $\varepsilon$, not on the size or complexity of the graph. However, in 1997, Timothy Gowers showed that the size of partition needed in the general case grows faster than an exponential tower of height polynomial in $1/\varepsilon $. Recently, many subcategories of hypergraphs, such as those with bounded VC dimension and those defined by semialgebraic sets of bounded complexity, have been shown to require only polynomial growth in terms of $1/\varepsilon $. We will be discussing the results of a paper by Artem Chernikov and Sergei Starchenko in which they develop and prove a model-theoretic analog of the regularity lemma for NIP hypergraphs, both finite and infinite, using finitely approximated Keisler measures. They also show that regular partitions are definable and, when VC dimension is bounded, their size can be bounded by a polynomial in $1/\varepsilon $. In addition, if the hypergraph is stable, all defective pairs can be eliminated. Alternatively, if the hypergraph is defined in a distal structure, there is a definable partition for which all pairs are homogenous in terms of the edge relation.
Wednesday April 26, 2017 at 10:00 AM in SEO 427