Regularity lemma for distal structures

Abstract

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 $p$-adics.