F Nous contacter


H 2 Graph regularity and incidence phenomena in distal structures

Auteurs : Chernikov, Artem (Auteur de la Conférence)
CIRM (Editeur )

Loading the player...
homogeneous subsets semialgebraic graphs o-minimal structures not the independence property (NIP) fields of positive characteristic distality Keisler measures generically stable measures distal Ramsey Szemerédi regularity lemma classification of regularity lemmas distal regularity lemma Erdos-Hajnal property Questions

Résumé : In recent papers by Alon et al. and Fox et al. it is demonstrated that families of graphs with a semialgebraic edge relation of bounded complexity have strong regularity properties and can be decomposed into very homogeneous semialgebraic pieces up to a small error (typical example is the incidence relation between points and lines on a real plane, or higher dimensional analogues). We show that in fact the theory can be developed for families of graphs definable in a structure satisfying a certain model theoretic property called distality, with respect to a large class of measures (this applies in particular to graphs definable in arbitrary o-minimal theories and in p-adics). (Joint work with Sergei Starchenko.)

Codes MSC :
03C45 - Classification theory, stability and related concepts [See also 03C48]
03C60 - Model-theoretic algebra [See also 08C10, 12Lxx, 13L05]
03C64 - Model theory of ordered structures; o-minimality

Informations sur la rencontre

Nom du congrès : Model Theory, Difference/Differential Equations and Applications / Théorie des modèles, équations différentielles et aux différences et applications
Organisteurs Congrès : Beyarslan, Özlem ; Hils, Martin ; Martin-Pizarro, Amador
Dates : 07/04/15 - 10/04/15
Année de la rencontre : 2015
URL Congrès : http://conferences.cirm-math.fr/1194.html

Citation Data

DOI : 10.24350/CIRM.V.18745203
Cite this video as: Chernikov, Artem (2015). Graph regularity and incidence phenomena in distal structures. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.18745203
URI : http://dx.doi.org/10.24350/CIRM.V.18745203


  1. [1] Alon, N., Pach, J., Pinchasi, R., Radoicic, R., & Sharir, M. (2005). Crossing patterns of semi-algebraic sets. Journal of Combinatorial Theory. Series A, 111(2), 310-326 - http://dx.doi.org/10.1016/j.jcta.2004.12.008

  2. [2] Basu, S. (2010). Combinatorial complexity in o-minimal geometry. Proceedings of the London Mathematical Society. Third Series, 100(2), 405-428 - http://dx.doi.org/10.1112/plms/pdp031

  3. [3] Chernikov, A., & Starchenko, S. Regularity lemma for distal graphs. Preprint -

  4. [4] Chernikov, A., & Simon, P. (2012). Externally definable sets and dependent pairs II. < arXiv:1202.2650> - http://arxiv.org/abs/1202.2650

  5. [5] Fox, J., Pach, J., & Suk, A. (2015). A polynomial regularity lemma for semi-algebraic hypergraphs and its applications in geometry and property testing. - http://arxiv.org/abs/1502.01730

  6. [6] Fox, J., Gromov, M., Lafforgue, V., Naor, A., & Pach, J. (2012). Overlap properties of geometric expanders. Journal für die Reine und Angewandte Mathematik, 671, 49-83 - http://dx.doi.org/10.1515/CRELLE.2011.157

  7. [7] Hrushovski, E., Pillay, A., & Simon, P. (2013). Generically stable and smooth measures in NIP theories. Transactions of the American Mathematical Society, 365(5), 2341-2366 - http://dx.doi.org/10.1090/S0002-9947-2012-05626-1

  8. [8] Simon, P. (2013). Distal and non-distal NIP theories. Annals of Pure and Applied Logic, 164(3), 294-318 - http://dx.doi.org/10.1016/j.apal.2012.10.015