Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-16T15:26:56.609Z 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: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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

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

[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