Notes on the stable regularity lemma. (English) Zbl 1529.03202
Summary: This is a short expository account of the regularity lemma for stable graphs proved by the authors, with some comments on the model theoretic context, written for a general logical audience.
MSC:
| 03C45 | Classification theory, stability, and related concepts in model theory |
| 03C65 | Models of other mathematical theories |
| 05C35 | Extremal problems in graph theory |
References:
| [1] | Ackerman, N., Freer, C., and Patel, R., Stable regularity for relational structures, preprint, 2014, arXiv:1712.09305. |
| [2] | Alon, N., Duke, R., Leffman, H., Rödl, V., and Yuster, R., The algorithmic aspects of the regularity lemma. Foundations of Computer Science, vol. 33 (1992), pp. 479-481. · Zbl 0915.05102 |
| [3] | Alon, N., Duke, R., Leffman, H., Rödl, V., and Yuster, R., The algorithmic aspects of the regularity lemma. Journal of Algorithms, vol. 16 (1994), pp. 80-109. · Zbl 0794.05119 |
| [4] | Alon, N., Fox, J., and Zhao, Y., Efficient arithmetic regularity and removal lemmas for induced bipartite patterns. Discrete Analysis, vol. 3 (2019), 14 pp. · Zbl 1472.11054 |
| [5] | Conlon, D. and Fox, J., Bounds for graph regularity and removal lemmas. Geometric and Functional Analysis, vol. 22 (2012), pp. 1192-1256. · Zbl 1256.05114 |
| [6] | Gowers, W. T., Lower bounds of tower type for Szemerédi’s uniformity lemma. Geometric and Functional Analysis, vol. 7 (1997), pp. 322-337. · Zbl 0876.05053 |
| [7] | Hodges, W., Model Theory, Encyclopedia of Mathematics, Cambridge University Press, Cambridge, 1993. · Zbl 0789.03031 |
| [8] | Komlós, J. and Simonovits, M., Szemerédi’s Regularity Lemma and its applications in graph theory, Combinatorics: Paul Erdös is Eighty, (Miklós, D., Sós, V. T. and Szönyi, T., editors), Bolyai Society Mathematical Studies, vol. 2, Keszthely, Hungary, 1996, pp. 295-352. · Zbl 0851.05065 |
| [9] | Lovász, L. and Szegedy, B., Regularity partitions and the topology of graphons, An Irregular Mind (Szemerédi is 70), Bolyai Society Mathematical Studies, vol. 21, Keszthely, Hungary, 2010, pp. 415-446. · Zbl 1242.05188 |
| [10] | Malliaris, M., Persistence and regularity in unstable model theory, Ph.D. thesis, Berkeley, 2009. |
| [11] | Malliaris, M., Edge distribution and density in the characteristic sequence. Annals of Pure and Applied Logic, vol. 162 (2010), no. 1, pp. 1-19. · Zbl 1225.03035 |
| [12] | Malliaris, M. and Shelah, S., Regularity lemmas for stable graphs. Transactions of the American Mathematical Society, vol. 366 (2014), pp. 1551-1585. First public version: arXiv:1102.3904 (Feb 2011). · Zbl 1283.05234 |
| [13] | Malliaris, M. and Shelah, S., Keisler’s order is not simple (and simple theories may not be either). Advances in Mathematics 2021, Paper No. 108036, 94 pp. · Zbl 1537.03037 |
| [14] | Malliaris, M. and Terry, C., On unavoidable induced subgraphs in large prime graphs. Journal of Graph Theory, vol. 88 (2018), no. 2, pp. 255-270. · Zbl 1391.05184 |
| [15] | Shelah, S., Classification Theory and the Number of Non-isomorphic Models, first ed., North-Holland, Amsterdam, 1978, rev. ed. 1990. · Zbl 0388.03009 |
| [16] | Szemerédi, E., On sets of integers containing no \(k\) elements in arithmetic progression. Acta Arithmetica, vol. 27 (1975), pp. 199-245. · Zbl 0303.10056 |
| [17] | Szemerédi, E., Regular partitions of graphs, Colloques Internationaux C.N.R.S. No. 260, Problèmes Combinatoires et Théorie Des Graphes, Univ. Orsay, Orsay, 1976, pp. 399-401. · Zbl 0413.05055 |
| [18] | Terry, C. and Wolf, J., Stable arithmetic regularity in the finite-field model. The Bulletin of the London Mathematical Society, vol. 51 (2019), no. 1, pp. 70-88. · Zbl 1462.11015 |
| [19] | Vapnik, V. and Chervonenkis, A., On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, vol. XVI (1971), no. 2, pp. 264-280. · Zbl 0247.60005 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
