Regularity lemma for distal structures

By Artem Chernikov, Sergei Starchenko. Journal of the European Mathematical Society (Print), 2015

78 citations recorded by the source corpus.

It is known that families of graphs with a semialgebraic edge relation of bounded complexity satisfy much stronger regularity properties than arbitrary graphs, and that they can be decomposed into very homogeneous semialgebraic pieces up to a small error (e.g., see [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.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/09c00b6c06e4baf56ecb8c236952929d76db190a