Submission date: 26 December 2017

Abstract:

We generalize the stable graph regularity lemma of Malliaris and Shelah to the case of finite structures in finite relational languages, e.g., finite hypergraphs. We show that under the model-theoretic assumption of stability, such a structure has an equitable regularity partition of size polynomial in the reciprocal of the desired accuracy, and such that for each k-ary relation and k-tuple of parts of the partition, the density is close to either 0 or 1. In addition, we provide regularity results for finite and Borel structures that satisfy a weaker notion that we call almost stability.

Mathematics Subject Classification:

Keywords and phrases:

Full text arXiv 1712.09305: pdf, ps.