Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-22T14:44:20.991Z Has data issue: false hasContentIssue false
  • English
  • Français

DOMINATION AND REGULARITY

Part of: Model theory

Published online by Cambridge University Press:  19 January 2021

ANAND PILLAY
ANAND PILLAY*
Affiliation:
DEPARTMENT OF MATHEMATICS UNIVERSITY OF NOTRE DAMENOTRE DAME, IN, USA E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We discuss the close relationship between structural theorems in (generalized) stability theory, and graph regularity theorems.

Keywords

Graph regularitystabilityNIP

MSC classification

Primary: 03C45: Classification theory, stability and related concepts
Secondary: 03C20: Ultraproducts and related constructions
Type
Articles
Information
Bulletin of Symbolic Logic , Volume 26 , Issue 2 , June 2020 , pp. 103 - 117
Copyright
© The Association for Symbolic Logic 2021

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Alon, N., Fischer, E., and Newman, I., Efficient testing of bipartite graphs for forbidden induced subgraphs . SIAM Journal on Computing , vol. 37 (2007), pp. 959–976.CrossRefGoogle Scholar
Chernikov, A. and Starchenko, S., Regularity lemma for distal structures . Journal of the European Mathematical Society , vol. 20 (2018), pp. 2437–2466.CrossRefGoogle Scholar
Chernikov, A. and Starchenko, S., Definable regularity lemmas for NIP hypergraphs, preprint, 2016.Google Scholar
Conant, G. and Pillay, A., Pseudofinite groups and VC-dimension, preprint, 2018.Google Scholar
Conant, G., Pillay, A., and Terry, C., A group version of stable regularity . Proceedings of Cambridge Philosophical Society , vol. 24 (2018), pp. 1–9.Google Scholar
Conant, G., Pillay, A., and Terry, C., Structure and regularity for subsets of groups with finite VC-dimension . Journal of the European Mathematical Society , to appear.Google Scholar
Fox, J., Gromov, M., Lafforgue, V., Naor, A., and Pach, J., Overlap properties of geometric expanders . Journal für die reine und angewandte Mathematik , vol. 671 (2012), pp. 49–83.Google Scholar
Fox, J., Pach, J., and Suk, A., Erdos-Hajnal conjecture for graphs with bounded VC-dimension . Discrete and Computational Geometry , vol. 61 (2019), pp. 809–829.CrossRefGoogle Scholar
Hrushovski, E., Peterzil, Y., and Pillay, A., Groups, measures, and the NIP . Journal of the American Mathematical Society , vol. 21 (2008), pp. 563–595.CrossRefGoogle Scholar
Hrushovski, E. and Pillay, A., ON NIP and invariant measures . Journal of the European Mathematical Society , vol. 13 (2011), pp. 1005–10061.CrossRefGoogle Scholar
Hrushovski, E., Pillay, A., and Simon, P., Generically stable and smooth measures in NIP theories . Transactions of the American Mathematical Society , vol. 365 (2013), pp. 2341–2366.CrossRefGoogle Scholar
Keisler, H. J., Measures and forking . Annals of Pure and Applied Logic , vol. 45 (1987), pp. 119–169.CrossRefGoogle Scholar
Lovasz, L. and Szegedy, B., Regularity partitions and the topology of graphons , An Irregular Mind: Szemerédi is 70 (Bárány, S., editor), Springer, New York, 2010, pp. 415–446.CrossRefGoogle Scholar
Malliaris, M. and Pillay, A., The stable regularity lemma, revisited . Proceedings of the American Mathematical Society , vol. 244 (2016), pp. 1761–1765.Google Scholar
Malliaris, M. and Shelah, S., Regularity lemmas for stable graphs . Transactions of the American Mathematical Society , vol. 366 (2014), pp. 1551–1585.CrossRefGoogle Scholar
Pillay, A., Geometric Stability Theory , Oxford University Press, Oxford, 1996.Google Scholar
Simon, P., A Guide to NIP Theories , Lecture Notes in Logic, vol. 44, ASL-Cambridge University Press, Cambridge, 2015.CrossRefGoogle Scholar
Simon, P., A note on “Regularity theorem for distal structures” . Proceedings of the American Mathematical Society , vol. 144 (2016), pp. 3573–3578.CrossRefGoogle Scholar
Terry, C. and Wolf, J., Stable arithmetic regularity in the finite field model . Bulletin of the London Mathematical Society , vol. 51 (2019), pp. 70–88.CrossRefGoogle Scholar