Abstract
Szemerédi’s Regularity Lemma is an important tool in discrete mathematics. It says that, in some sense, all graphs can be approximated by random-looking graphs. Therefore the lemma helps in proving theorems for arbitrary graphs whenever the corresponding result is easy for random graphs. In the last few years more and more new results were obtained by using the Regularity Lemma, and also some new variants and generalizations appeared. Komlós and Simonovits have written a survey on the topic [96]. The present survey is, in a sense, a continuation of the earlier survey. Here we describe some sample applications and generalizations. To keep the paper self-contained we decided to repeat (sometimes in a shortened form) parts of the first survey, but the emphasis is on new results.
Research supported in part by the NSF grant DMS-9801396.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. Ajtai, J. Komlós, M. Simonovits and E. Szemerédi, Solution of the Erdős-Sós Conjecture, in preparation.
N. Alon, R. Duke, H. Leffman, V. Rödl, R. Yuster, The algorithmic aspects of the regularity lemma, FOCS 33 (1992), 479-481, Journal of Algorithms 16 (1994), 80–109.
N. Alon, E. Fischer, 2-factors in dense graphs, Discrete Math.
N. Alon, R. Yuster, Almost H-factors in dense graphs, Graphs and Combinatorics 8 (1992), 95–102.
N. Alon, R. Yuster, H-factors in dense graphs, J. Combinatorial Theory B66 (1996), 269–282.
L. Babai, M. Simonovits, J. Spencer, Extremal subgraphs of random graphs, Journal of Graph Theory 14 (1990), 599–622.
V. Bergelson, A. Leibman, Polynomial extension of van der Waerden’s and Szemerédi’s theorem.
B. Bollobás, Extremal graph theory, Academic Press, London (1978).
Béla Bollobás, The work of William Timothy Gowers, Proceedings of the International Congress of Mathematicians, Vol. I (Berlin, 1998), Doc. Math. 1998, Extra Vol. I, 109-118 (electronic).
B. Bollobás, P. Erdős, On a Ramsey-Turán type problem, Journal of Combinatorial Theory B21 (1976), 166–168.
B. Bollobás, P. Erdős, M. Simonovits, E. Szemerédi, Extremal graphs without large forbidden subgraphs, Annals of Discrete Mathematics 3 (1978), 29–41, North-Holland.
B. Bollobás, A. Thomason, The structure of hereditary properties and colourings of random graphs. Combinatorica 20 (2000), 173–202.
W. G. Brown, P. Erdős, M. Simonovits, Extremal problems for directed graphs, Journal of Combinatorial Theory B15 (1973), 77–93.
W. G. Brown, P. Erdős, M. Simonovits, Inverse extremal digraph problems, Colloq. Math. Soc. J. Bolyai 37 (Finite and Infinite Sets), Eger (Hungary) 1981, Akad. Kiadó, Budapest (1985), 119–156.
W. G. Brown, P. Erdős, M. Simonovits, Algorithmic solution of extremal digraph problems, Transactions of the American Math. Soc. 292/2 (1985), 421–449.
W. G. Brown, P. Erdős, V. T. Sós, Some extremal problems on r-graphs, New directions in the theory of graphs (Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich, 1971), 53–63. Academic Press, New York, 1973.
W. G. Brown, P. Erdős, V. T. Sós, On the existence of triangulated spheres in 3-graphs, and related problems, Period. Math. Hungar. 3 (1973), 221–228.
W. G. Brown, M. Simonovits, Digraph extremal problems, hypergraph extremal problems, and densities of graph structures, Discrete Mathematics 48 (1984), 147–162.
S. Burr, P. Erdős, P. Frankl, R. L. Graham, V. T. Sós, Further results on maximal antiramsey graphs, Proc. Kalamazoo Combin. Conf. (1989), 193–206.
S. Burr, P. Erdős, R. L. Graham, V. T. Sós, Maximal antiramsey graphs and the strong chromatic number (The nonbipartite case) Journal of Graph Theory 13 (1989), 163–182.
L. Caccetta, R. Häggkvist, On diameter critical graphs, Discrete Mathematics 28 (1979), 223–229.
Fan R. K. Chung, Regularity lemmas for hypergraphs and quasi-randomness, Random Structures and Algorithms 2 (1991), 241–252.
F. R. K. Chung, R. L. Graham, R. M. Wilson, Quasi-random graphs, Combinatorica 9 (1989), 345–362.
V. Chvátal, V. Rödl, E. Szemerédi, W. T. Trotter Jr., The Ramsey number of a graph with bounded maximum degree, Journal of Combinatorial Theory B34 (1983), 239–243.
V. Chvátal, E. Szemerédi, On the Erdős-Stone theorem, Journal of the London Math. Soc. 23 (1981), 207–214.
V. Chvátal, E. Szemerédi, Notes on the Erdős-Stone theorem, Combinatorial Mathematics, Annals of Discrete Mathematics 17 (1983), (Marseille-Luminy, 1981), 183–190, North-Holland, Amsterdam-New York, 1983.
K. Corrádi, A. Hajnal, On the maximal number of independent circuits in a graph, Acta Math. Acad. Sci. Hung. 14 (1963), 423–439.
W. Deuber, Generalizations of Ramsey’s theorem, Proc. Colloq. Math. Soc. János Bolyai 10 (1974), 323–332.
G. A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. 2 (1952), 68–81.
Duke, Richard A., Hanno Lefmann, Hanno, Vojtěch Rödl, A fast approximation algorithm for computing the frequencies of subgraphs in a given graph, SIAM J. Comput. 24 (1995), 598–620.
R. A. Duke, V. Rödl, On graphs with small subgraphs of large chromatic number, Graphs Combin. 1 (1985), 91–96.
R. A. Duke, V. Rödl, The Erdös-Ko-Rado theorem for small families, J. Combin. Theory Ser. A65 (1994), 246–251.
P. Erdős, Some recent results on extremal problems in graph theory, Results, International Symposium, Rome (1966), 118–123.
P. Erdős, On some new inequalities concerning extremal properties of graphs, Theory of Graphs, Proc. Coll. Tihany, Hungary (P. Erdős and G. Katona eds.) Acad. Press N. Y. (1968), 77–81.
P. Erdős, On some extremal problems on r-graphs, Discrete Mathematics 1 (1971), 1–6.
P. Erdős, Some old and new problems in various branches of combinatorics, Proc. 10th Southeastern Conf. on Combinatorics, Graph Theory and Computation, Boca Raton (1979) Vol I., Congressus Numerantium 23 (1979), 19–37.
P. Erdős, On the combinatorial problems which I would most like to see solved, Combinatorica 1 (1981), 25–42.
P. Erdős, P. Frankl, V. Rödl, The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent, Graphs and Combinatorics 2 (1986), 113–121.
P. Erdős, Z. Füredi, M. Loebl, V. T. Sós, Studia Sci. Math. Hung. 30 (1995), 47–57. (Identical with the book Combinatorics and its applications to regularity and irregularity of structures, W. A. Deuber and V. T. Sós eds., Akadémiai Kiadó, 47-58.)
P. Erdős, T. Gallai, On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hung. 10 (1959), 337–356.
P. Erdős, A. Hajnal, On complete topological subgraphs of certain graphs, Annales Univ. Sci. Budapest 7 (1969), 193–199.
P. Erdős, A. Hajnal, L. Pósa, Strong embedding of graphs into colored graphs, Proc. Colloq. Math. Soc. János Bolyai 10 (1975), 585–595.
P. Erdős, A. Hajnal, M. Simonovits, V. T. Sós, E. Szemerédi, Turán-Ramsey theorems and simple asymptotically extremal structures, Combinatorica 13 (1993), 31–56.
P. Erdős, A. Hajnal, M. Simonovits, V. T. Sós, E. Szemerédi, Turán-Ramsey theorems for Kp-stability numbers, Proc. Cambridge, also in Combinatorics, Probability and Computing 3 (1994) (P. Erdős birthday meeting), 297–325.
P. Erdős, A. Hajnal, V. T. Sós, E. Szemerédi, More results on Ramsey-Turán type problems, Combinatorica 3 (1983), 69–81.
P. Erdős, M. Simonovits, A limit theorem in graph theory, Studia Sci. Math. Hung. 1 (1966), 51–57.
P. Erdős, M. Simonovits, The chromatic properties of geometric graphs, Ars Combinatoria 9 (1980), 229–246.
P. Erdős, M. Simonovits, Supersaturated graphs and hypergraphs, Combinatorica 3 (1983), 181–192.
P. Erdős, M. Simonovits, How many colours are needed to colour every pentagon of a graph in five colours? (to be published).
P. Erdős, V. T. Sós, The tree conjecture, Mentioned in P. Erdős, Extremal problems in graph theory, Theory of graphs and its applications, Proc. of the Symposium held in Smolenice in June 1963, 29–38.
P. Erdős, V. T. Sós, Some remarks on Ramsey’s and Turán’s theorem, Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969), 395–404, North-Holland, Amsterdam, 1970.
P. Erdős, A. H. Stone, On the structure of linear graphs, Bull. Amer. Math. Soc. 52 (1946), 1089–1091.
P. Erdős, P. Turán, On some sequences of integers, J. London Math. Soc. 11 (1936), 261–264.
G. Fan, R. Häggkvist, The square of a hamiltonian cycle, SIAM J. Disc. Math.
G. Fan, H. A. Kierstead, The square of paths and cycles, Journal of Combinatorial Theory B63 (1995), 55–64.
G. Fan, H. A. Kierstead, The square of paths and cycles II.
R. J. Faudree, R. J. Gould, M. Jacobson, On a problem of Pósa and Seymour.
R. J. Faudree, R. J. Gould, M. S. Jacobson, R. H. Schelp, Seymour’s conjecture, Advances in Graph Theory (V. R. Kulli ed.), Vishwa International Publications (1991), 163–171.
P. Frankl, Z. Füredi, Exact solution of some Turán-type problems, Journal of Combinatorial Theory A45 (1987), 226–262.
P. Frankl, J. Pach, An extremal problem on Kr-free graphs, Journal of Graph Theory 12 (1988), 519–523.
P. Frankl, V. Rödl, The Uniformity Lemma for hypergraphs, Graphs and Combinatorics 8 (1992), 309–312.
Alan Frieze, Ravi Kannan, Quick approximation to matrices and applications, Combinatorica 19 (1999), 175–220.
Alan Frieze, Ravi Kannan, A simple algorithm for constructing Szemerédi’s regularity partition, Electron. J. Combin. 6 (1999), Research Paper 17 (electronic).
Z. Füredi, Turán type problems, in Surveys in Combinatorics (1991), Proc. of the 13th British Combinatorial Conference, (A. D. Keedwell ed.) Cambridge Univ. Press. London Math. Soc. Lecture Note Series 166 (1991), 253–300.
Z. Füredi, The maximum number of edges in a minimal graph of diameter 2, Journal of Graph Theory 16 (1992), 81–98.
H. Fcurstenberg, Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions, Journal d’Analyse Math. 31 (1977), 204–256.
H. Fürstenberg, A polynomial Szemerédi theorem, Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), 1–16, Bolyai Soc. Math. Stud., 2, János Bolyai Math. Soc., Budapest, 1996
H. Fürstenberg, Y. Katznelson, Idempotents in compact semigroups and Ramsey theory, Israel Journal of Mathematics 68 (1989), 257–270.
H. Fürstenberg, Y. Katznelson, A density version of the Hales-Jewett theorem, Journal d'Analyse Math. 57 (1991), 64–119.
W. T. Gowers, Lower bounds of tower type for Szemerédi’s uniformity lemma, Geom. Funct. Anal. 7 (1997), 322–337.
R. L. Graham, B. L. Rothschild, J. Spencer, Ramsey Theory, Wiley Interscience, Series in Discrete Mathematics (1980).
A. Hajnal, W. Maass, Gy. Turán, On the communication complexity of graph properties, 20th STOC, Chicago (1988), 186–191.
A. Hajnal, E. Szemerédi, Proof of a conjecture of Erdős, Combinatorial Theory and its Applications vol. II (P. Erdős, A. Rényi and V. T. Sós eds.), Colloq. Math. Soc. J. Bolyai 4, North-Holland, Amsterdam (1970), 601–623.
P. E. Haxell, Y. Kohayakawa, The size-Ramsey number of trees, Israel J. Math. 89 (1995), 261–274.
P. E. Haxell, Y. Kohayakawa, On an anti-Ramsey property of Ramanujan graphs, Random Structures and Algorithms 6 (1995), 417–431.
P. E. Haxell, Y. Kohayakawa, T. Luczak, The induced size-Ramsey number of cycles, Combinatorics, Probability and Computing 4 (1995), 217–239.
P. E. Haxell, Y. Kohayakawa, T. Luczak, Turán’s extremal problem in random graphs: forbidding even cycles, Journal of Combinatorial Theory B64 (1995), 273–287.
P. E. Haxell, Y. Kohayakawa, T. Luczak, Turán’s extremal problem in random graphs: forbidding odd cycles, Combinatorica 16 (1996), 107–122.
P. E. Haxell, T. Luczak, P. W. Tingley, Ramsey Numbers for Trees of Small Maximum Degree.
D. R. Heath-Brown, Integer sets containing no arithmetic progressions, J. London Math. Soc. 35 (1987), 385–394.
Y. Kohayakawa, The Regularity Lemma of Szemerédi for sparse graphs, manuscript, August 1993.
Y. Kohayakawa, Szemerédi’s regularity lemma for sparse graphs, Foundations of computational mathematics (Rio de Janeiro) (1997), 216–230, Springer, Berlin.
Y. Kohayakawa, B. Kreuter, Threshold functions for asymmetric Ramsey properties involving cycles, Random Structures Algorithms 11 (1997), 245–276.
Y. Kohayakawa, T. Luczak, V. Rödl, Arithmetic progressions of length three in subsets of a random set, Acta Arithmetica, 75 (1996), 133–163.
Y. Kohayakawa, T. Luczak, V. Rödl, Arithmetic progressions of length three in subsets of a random set, Acta Arith. 75 (1996), 133–163.
Y. Kohayakawa, T. Luczak, V. Rödl, On K 4-free subgraphs of random graphs, Combinatorica 17 (1997), 173–213.
J. Komlós, The blow-up lemma, Recent trends in combinatorics (Mátraháza, 1995), Combin. Probab. Comput. 8 (1999), 161–176.
J. Komlós, Tiling Turán Theorems, Combinatorica 20 (2000), 203–218.
J. Komlós, G. N. Sárközy, E. Szemerédi, Proof of a packing conjecture of Bollobás, AMS Conference on Discrete Mathematics, DeKalb, Illinois (1993), Combinatorics, Probability and Computing 4 (1995), 241–255.
J. Komlós, G. N. Sárközy, E. Szemerédi, On the square of a Hamiltonian cycle in dense graphs, Proceedings of the Seventh International Conference on Random Structures and Algorithms (Atlanta, GA, 1995), Random Structures and Algorithms 9 (1996), 193–211.
J. Komlós, G. N. Sárközy, E. Szemerédi, Blow-up Lemma, Combinatorica 17 (1997), 109–123.
J. Komlós, G. N. Sárközy, E. Szemerédi, An algorithmic version of the blow-up lemma, Random Structures Algorithms 12 (1998), 297–312.
J. Komlós, G. N. Sárközy, E. Szemerédi, On the Pósa-Seymour conjecture, J. Graph Theory 29 (1998), 167–176.
János Komlós, Gábor Sárközy, Endre Szemerédi, Proof of the Seymour conjecture for large graphs, Ann. Comb. 2 (1998), 43–60.
J. Komlós, G. N. Sárközy, E. Szemerédi, Proof of the Alon-Yuster conjecture, Random Structures and Algorithms.
J. Komlós, M. Simonovits,Szemerédi’s regularity lemma and its applications in graph theory, Bolyai Society Mathematical Studies 2, Combinatorics, Paul Erdős is Eighty (Volume 2) (D. Miklós, V. T. Sós, T. Szőnyi eds.), Keszthely (Hungary) (1993), Budapest (1996), 295–352.
L. Lovász, M. Simonovits, On the number of complete subgraphs of a graph I, Proc. Fifth British Combin. Conf. Aberdeen (1975), 431–442.
L. Lovász, M. Simonovits, On the number of complete subgraphs of a graph II, Studies in Pure Math (dedicated to the memory of P. Turán), Akadémiai Kiadó and Birkhäuser Verlag (1983), 459–495.
T. Luczak, R(C n , C n , C n ) ≤ (4 + o(1))n, J. Combin. Theory B75 (1999), 174–187.
Luczak, Tomasz; Rödl, Vojtěch; Szemerédi, Endre, Partitioning two-coloured complete graphs into two monochromatic cycles, Combin. Probab. Comput. 7 (1998), 423–436.
J. Nešetřil, V. Rödl, Partition theory and its applications, in Surveys in Combinatorics (Proc. Seventh British Combinatorial Conf., Cambridge, 1979), pp. 96–156, (B. Bollobás ed.), London Math. Soc. Lecture Notes Series, Cambridge Univ. Press, Cambridge-New York, 1979.
P. Pudlák, J. Sgall, An upper bound for a communication game, related to time-space tradeoffs, Electronic Colloquium on Computational Complexity, TR 95-010, (1995).
K. F. Roth, On certain sets of integers (II), J. London Math. Soc. 29 (1954), 20–26.
K. F. Roth, Irregularities of sequences relative to arithmetic progressions (III), Journal of Number Theory 2 (1970), 125–142.
K. F. Roth, Irregularities of sequences relative to arithmetic progressions (IV), Periodica Math. Hung. 2 (1972), 301–326.
V. Rödl, A generalization of Ramsey Theorem and dimension of graphs, Thesis, 1973, Charles Univ. Prague; see also: A generalization of Ramsey Theorem for graphs, hypergraphs and block systems, Zielona Gora (1976), 211–220.
V. Rödl, On universality of graphs with uniformly distributed edges, Discrete Mathematics 59 (1986), 125–134.
V. Rödl, Sparse Regularity, Personal communication.
V. Rödl, A. Ruciński, Random graphs with monochromatic triangles in every edge coloring, Random Structures and Algorithms 5 (1994), 253–270.
V. Rödl, A. Ruciński, Threshold functions for Ramsey properties, J. Amer. Math. Soc. 8 (1995), 917–942.
I. Z. Ruzsa, E. Szemerédi, Triple systems with no six points carrying three triangles, Combinatorics (Keszthely, 1976), 18 (1978), Vol. II., 939–945, North-Holland, Amsterdam-New York.
G. N. Sárközy, Fast parallel algorithm for finding Hamiltonian cycles and trees in graphs.
P. Seymour, Problem section, Combinatorics: Proceedings of the British Combinatorial Conference 1973 (T. P. McDonough and V. C. Mavron eds.), Cambridge University Press (1974), 201–202.
A. F. Sidorenko, Boundedness of optimal matrices in extremal multigraph and digraph problems, Combinatorica 13 (1993), 109–120.
M. Simonovits, A method for solving extremal problems in graph theory, Theory of graphs, Proc. Coll. Tihany (1966) (P. Erdős and G. Katona eds.), Acad. Press, N.Y. (1968), 279–319.
M. Simonovits, Extremal graph problems with symmetrical extremal graphs, additional chromatic conditions, Discrete Mathematics 7 (1974), 349–376.
M. Simonovits, Extremal graph theory, Selected Topics in Graph Theory (L. Beineke and R. Wilson eds.) Academic Press, London, New York, San Francisco (1985), 161–200.
M. Simonovits, V. T. Sós, Szemerédi’s partition and quasirandomness, Random Structures and Algorithms 2 (1991), 1–10.
M. Simonovits and V. T. Sós, Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs, Combinatorica 17 (1997), 577–596.
M. Simonovits and V. T. Sós, Hereditarily extended properties, quasi-random graphs and induced subgraphs, to be published.
M. Simonovits and V. T. Sós, Ramsey-Turán theory, Proc. Prague Meeting, Fifth Czech-Slovak International Symposia, Discrete Mathematics, to appear.
V. T. Sós, On extremal problems in graph theory, Proc. Calgary International Conf. on Combinatorial Structures and their Application, Gordon and Breach, N. Y. (1969), 407–410.
V. T. Sós, Interaction of Graph Theory and Number Theory, in Proc. Conf. Paul Erdős and His Mathematics, Budapest, 1999. Springer Verlag, 2001.
E. Szemerédi, On sets of integers containing no four elements in arithmetic progression, Acta Math. Acad. Sci. Hung. 20 (1969), 89–104.
E. Szemerédi, On graphs containing no complete subgraphs with 4 vertices (in Hungarian), Matematikai Lapok 23 (1972), 111–116.
E. Szemerédi, On sets of integers containing no k elements in arithmetic progression, Acta Arithmetica 27 (1975), 199–245.
E. Szemerédi, Regular partitions of graphs, Colloques Internationaux C.N.R.S. No 260-Problèmes Combinatoires et Théorie des Graphes, Orsay (1976), 399–401.
E. Szemerédi, Integer sets containing no arithmetic progressions, Acta Math. Acad. Sci. Hung. 56 (1990), 155–158.
A. Thomason, Pseudo-random graphs, in Proc. of Random Graphs, Poznán (1985) (M. Karoński ed.), Annals of Discr. Math. (North-Holland) 33 (1987), 307–331. See also: Dense expanders and bipartite graphs, Discrete Mathematics 75 (1989), 381-386.
Pál Turán, On an extremal problem in graph theory (in Hungarian), Matematikaiés Fizikai Lapok 48 (1941), 436–452.
B. L. Van der Waerden, Beweis einer Baudetschen Vermutung, Nieuw Archief voor Wiskunde 15 (1927), 212–216.
R. Yuster, The number of edge colorings with no monochromatic triangle, J. Graph Theory 21 (1996), 441–452.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Komlós, J., Shokoufandeh, A., Simonovits, M., Szemerédi, E. (2002). The Regularity Lemma and Its Applications in Graph Theory. In: Khosrovshahi, G.B., Shokoufandeh, A., Shokrollahi, A. (eds) Theoretical Aspects of Computer Science. TACSci 2000. Lecture Notes in Computer Science, vol 2292. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45878-6_3
Download citation
DOI: https://doi.org/10.1007/3-540-45878-6_3
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43328-6
Online ISBN: 978-3-540-45878-4
eBook Packages: Springer Book Archive