In a series of papers by Alon, Conlon, Fox, Gromov, Naor, Pach, Pinchasi, Radoi, Sharir, Sudakov, Lafforgue, Suk and others it is demonstrated that families of graphs with the edge relation given by a semialgebraic relation of bounded complexity satisfy much stronger regularity properties than arbitrary graphs, and can be decomposed into very homogeneous semialgebraic pieces modulo a small mistake (for example the incidence relation between points and lines on the real plane, or higher dimensional analogues). We show that in fact the whole theory can be developed for families of graphs whose edge relation is uniformly definable in a structure satisfying a certain model theoretic property called distality, with respect to arbitrary generically stable measures rather than just the counting ones. Moreover, distality characterizes these strong regularity properties. This applies in particular to definable graphs in all o-minimal and weakly o-minimal theories, and in p-adics.Joint work with Sergei Starchenko.
- Séminaire Géométrie et théorie des modèles