Regularity lemma for distal structures

  • Artem Chernikov

    University of California at Los Angeles, USA
  • Sergei Starchenko

    University of Notre Dame, USA
Regularity lemma for distal structures cover
Download PDF

A subscription is required to access this article.


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–2466

DOI 10.4171/JEMS/816