Hostname: page-component-745bb68f8f-s22k5 Total loading time: 0 Render date: 2025-02-12T04:17:39.805Z Has data issue: false hasContentIssue false
  • English
  • Français

Szemerédi's Regularity Lemma for Matrices and Sparse Graphs

Published online by Cambridge University Press:  03 February 2011

ALEXANDER SCOTT
ALEXANDER SCOTT*
Affiliation:
Mathematical Institute, 24-29 St Giles', Oxford, OX1 3LB, UK (e-mail: scott@maths.ox.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Szemerédi's Regularity Lemma is an important tool for analysing the structure of dense graphs. There are versions of the Regularity Lemma for sparse graphs, but these only apply when the graph satisfies some local density condition. In this paper, we prove a sparse Regularity Lemma that holds for all graphs. More generally, we give a Regularity Lemma that holds for arbitrary real matrices.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 20 , Issue 3 , May 2011 , pp. 455 - 466
Copyright
Copyright © Cambridge University Press 2011

References

[1]Bollobás, B. and Riordan, O. (2005) Metrics for sparse graphs. In Surveys in Combinatorics 2009, Vol. 365 of London Mathematical Society Lecture Notes, Cambridge University Press, pp. 211–287.Google Scholar
[2]Gerke, S. and Steger, A. (2005) The sparse regularity lemma and its applications. In Surveys in Combinatorics 2005, Vol. 327 of London Mathematical Society Lecture Notes, Cambridge University Press, pp. 227–258.CrossRefGoogle Scholar
[3]Kohayakawa, Y. (1997) Szemerédi's regularity lemma for sparse graphs. In Foundations of Computational Mathematics (Rio de Janeiro), Springer, pp. 216–230.CrossRefGoogle Scholar
[4]Kohayakawa, Y. and Rödl, V. (2003) Szemerédi's regularity lemma and quasi-randomness. In Recent Advances in Algorithms and Combinatorics, Vol. 11 of CMS Books Math./Ouvrages Math. SMC, Springer, pp. 289–351.Google Scholar
[5]Komlós, J. and Simonovits, M. (1996) Szemerédi's regularity lemma and its applications in graph theory. In Combinatorics: Paul ErdHős is Eighty, Vol. 2 (Keszthely 1993), Vol. 2 of Bolyai Society Mathematical Studies, János Bolyai Mathematical Society, pp. 295–352.Google Scholar
[6]Łuczak, T. (2000) On triangle-free random graphs. Random Struct. Alg. 16 260–276.3.0.CO;2-Q>CrossRefGoogle Scholar
[7]Szemerédi, E. (1978) Regular partitions of graphs. In Problèmes Combinatoires et Théorie des Graphes (Colloq. Internat. CNRS, Orsay 1976), CNRS, pp. 399–401.Google Scholar