It is known that families of graphs with a semialgebraic edge relation of bounded complexity satisfy much stronger regularity properties than arbitrary graphs, and can be decomposed into very homogeneous semialgebraic pieces up to a small error (see e.g. [33, 2, 16, 18]). We show that similar results can be obtained for families of graphs with the edge relation uniformly definable in a structure satisfying a certain model-theoretic property called distality, with respect to a large class of generically stable measures. Moreover, distality characterizes these strong regularity properties. This applies in particular to graphs definable in arbitrary o-minimal structures and in -adics.
Cite this article
Artem Chernikov, Sergei Starchenko, Regularity lemma for distal structures. J. Eur. Math. Soc. 20 (2018), no. 10, pp. 2437–2466DOI 10.4171/JEMS/816