Skip to main content
SpringerLink
Log in

Blow-up Lemma

  • Published:
Combinatorica Aims and scope Submit manuscript

Abstract

Regular pairs behave like complete bipartite graphs from the point of view of bounded degree subgraphs.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. N. Alon, R. Duke, H. Leffman, V. Rödl, andR. Yuster: Algorithmic aspects of the regularity lemma.FOCS,33 (1993), 479–481; Journal of Algorithms,16 (1994), 80–109.

    Google Scholar 

  2. N. Alon andE. Fischer: 2-factors in dense graphs, Discrete Math., to appear.

  3. N. Alon, S. Friedland, G. Kalai: Regular subgraphs of almost regular graphs,J. Combinatorial Theory, B37 (1984), 79–91. See alsoN. Alon, S. Friedland, G. Kalai: Every 4-regular graph plus an edge contains a 3-regular subgraph,J. Combinatorial Theory, B37 (1984), 91–92.

    Google Scholar 

  4. N. Alon andR. Yyster: AlmostH-factors in dense graphs,Graphs and Combinatorics,8 (1992), 95–102.

    Google Scholar 

  5. N. Alon andR. Yuster:H-factors in dense graphs,J. Combinatorial Theory, Ser. B, to appear.

  6. V. Ghvátal, V. Rödl, E. Szemerédi, andW. T. Trotter Jr.: The Ramsey number of a graph with bounded maximum degree,Journal of Combinatorial Theory, B34 (1983), 239–243.

    Google Scholar 

  7. K. Corrádi andA. Hajnal: On the maximal number of independent circuits in a graph,Acta Math. Acad. Sci. Hung.,14 (1963), 423–439.

    Google Scholar 

  8. T. Kővári, Vera T. Sós, andP. Turán: On a problem of Zarankiewicz,Colloq. Math.,3 (1954), 50–57.

    Google Scholar 

  9. P. Erdős andA. H. Stone: On the structure of linear graphs,Bull. Amer. Math. Soc.,52 (1946), 1089–1091.

    Google Scholar 

  10. A. Hajnal andE. 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.

    Google Scholar 

  11. J. Komlós, G. N. Sárközy, andE. 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.

    Google Scholar 

  12. J. Komlós, G. N. Sárközy, andE. Szemerédi: On the Pósa-Seymour conjecture, submitted to theJournal of Graph Theory.

  13. J. Komlós, G. N. Sárközy, andE. Szemerédi: On the square of a Hamiltonian cycle in dense graphs, Proceedings of Atlanta'95,Random Structures and Algorithms,9 (1996), 193–211.

    Google Scholar 

  14. J. Komlós, G. N. Sárközy, andE. Szemerédi: Proof of the Alon-Yuster conjecture, in preparation.

  15. J. Komlós andM. 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.

  16. 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.

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Rutgers University, 08903, New Brunswick, NJ

    János Komlós

  2. Department of Computer Science, Rutgers University, 08903, New Brunswick, NJ

    Gábor N. Sárközy

  3. Hungarian Academy of Sciences, Budapest, Hungary

    Endre Szemerédi

Authors
  1. János Komlós
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Gábor N. Sárközy
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Endre Szemerédi
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Komlós, J., Sárközy, G.N. & Szemerédi, E. Blow-up Lemma. Combinatorica 17, 109–123 (1997). https://doi.org/10.1007/BF01196135

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01196135

Mathematics Subject Classification (1991)

Search

Navigation