Submission date: 6 July 2015.

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 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.

Mathematics Subject Classification: Primary 03C45, 03C98, 05C35, 05C69, 05D10, 05C25, Secondary 14P10, 03C64

Keywords and phrases:

Full text arXiv 1507.01482: pdf, ps.