Regularity lemma for distal structures (Q1989603): Difference between revisions

Summary: 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. [\textit{J. Pach} and \textit{J. Solymosi}, J. Comb. Theory, Ser. A 96, No. 2, 316--325 (2001; Zbl 0989.05031); \textit{N. Alon} et al., J. Comb. Theory, Ser. A 111, No. 2, 310--326 (2005; Zbl 1099.14048); \textit{J. Fox} et al., J. Reine Angew. Math. 671, 49--83 (2012; Zbl 1306.05171); \textit{J. Fox} et al., SIAM J. Comput. 45, No. 6, 2199--2223 (2016; Zbl 1353.05090)]). 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.