Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Density of Monochromatic Infinite Subgraphs

  • Published:
Combinatorica Aims and scope Submit manuscript

Abstract

For any countably infinite graph G, Ramsey’s theorem guarantees an infinite monochromatic copy of G in any r-coloring of the edges of the countably infinite complete graph Kℕ. Taking this a step further, it is natural to wonder how “large” of a monochromatic copy of G we can find with respect to some measure - for instance, the density (or upper density) of the vertex set of G in the positive integers. Unlike finite Ramsey theory, where this question has been studied extensively, the analogous problem for infinite graphs has been mostly overlooked.

In one of the few results in the area, Erdős and Galvin proved that in every 2-coloring of Kℕ, there exists a monochromatic path whose vertex set has upper density at least 2/3, but it is not possible to do better than 8/9. They also showed that for some sequence εn → 0, there exists a monochromatic path P such that for infinitely many n, the set (1,2,...,n contains the first \(\left(\frac{1}{3+\sqrt{3}}-\epsilon_n\right)n\) vertices of P, but it is not possible to do better than 2n/3. We improve both results, in the former case achieving an upper density at least 3/4 and in the latter case obtaining a tight bound of 2/3. We also consider related problems for directed paths, trees (connected subgraphs), and a more general result which includes locally finite graphs for instance.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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. P. Allen, B. Roberts and J. Skokan: Ramsey numbers of squares of paths, Electronic Notes in Discrete Mathematics 49 (2015), 637–641.

    Article  Google Scholar 

  2. F. Benevides, T. Luczak, J. Skokan, A. Scott and M. White: Monochromatic cycles in 2-coloured graphs, Combinatorics, Probability, and Computing, 21 (2012), 57–87.

    Article  MathSciNet  Google Scholar 

  3. C. Berge: Graphs and Hypergraphs, second revised edition, Amsterdam: North-Holland Publishing Co., 1976.

    MATH  Google Scholar 

  4. C. Chvatál, V. Rödl, E. Szemerédi and W. T. Trotter: The Ramsey number of a graph with bounded maximum degree, Journal of Combinatorial Theory, Series B 34 (1983), 239–243.

    Article  MathSciNet  Google Scholar 

  5. J. Corsten: Personal communication.

  6. M. Elekes, D. Soukup, L. Soukup and Z. Szentmiklóssy: Decompositions of edge-colored infinite complete graphs into monochromatic paths, Discrete Mathematics 340 (2017), 2053–2069.

    Article  MathSciNet  Google Scholar 

  7. P. Erdős: Some remarks on Ramsay’s theorem, Canadian Mathematical Bulletin 7 (1964), 619–622.

    Article  MathSciNet  Google Scholar 

  8. P. Erdős and F. Galvin: Some Ramsey-type theorems, Discrete Mathematics 87 (1991), 261–269.

    Article  MathSciNet  Google Scholar 

  9. P. Erdős and F. Galvin: Monochromatic infinite paths, Discrete Mathematics 113 (1993), 59–70.

    Article  MathSciNet  Google Scholar 

  10. P. Erdős, A. Gyárfás and L. Pyber: Vertex coverings by monochromatic cycles and trees, Journal of Combinatorial Theory, Series B 51 (1991), 90–95.

    Article  MathSciNet  Google Scholar 

  11. I. Farah: Semiselective coideals, Mathematika 45 (1998), 79–103.

    Article  MathSciNet  Google Scholar 

  12. L. Gerencsér and A. Gyárfás: On Ramsey-type problems, Ann. Sci. Budapest. Ëotvös Sect. Math 10 (1967), 167–170.

    MathSciNet  MATH  Google Scholar 

  13. H. Guggiari: Monochromatic paths in the complete symmetric infinite digraph, manuscript, arXiv:1710.10900, (2017).

    Google Scholar 

  14. A. Gyárfás: Partition covers and blocking sets in hypergraphs, MTA SZTAKI Tanulmányok 71, 1977.

  15. A. Gyárfás and J. Lehel: A Ramsey-type problem in directed and bipartite graphs, Periodica Mathematica Hungarica 3 (1973), 299–304.

    Article  MathSciNet  Google Scholar 

  16. A. Gyárfás, M. Ruszinkó, G. Sárközy and E. Szemerédi: Three-color Ramsey numbers for paths, Combinatorica 27 (2007), 35–69.

    Article  MathSciNet  Google Scholar 

  17. A. xGyárfás and G. Sárközy: Star Versus Two Stripes Ramsey Numbers and a Conjecture of Schelp, Combinatorics, Probability and Computing 21 (2012), 179–186.

    Article  MathSciNet  Google Scholar 

  18. A. Gyárfás, G. Sárközy and E. Szemerédi: The Ramsey number of diamond-matchings and loose cycles in hypergraphs, Electron. J. Combin 15 (2008), #R126.

  19. P. Haxell, T. Luczak, Y. Peng, V. Rödl, A. Ruciński and J. Skokan: The Ramsey number for 3-uniform tight hypergraph cycles, Combinatorics, Probability and Computing 18 (2009), 165–203.

    Article  MathSciNet  Google Scholar 

  20. P. Haxell, T. Luczak, Y. Peng, V. Rödl, A. Ruciński, M. Simonovits and J. Skokan: The Ramsey number for hypergraph cycles I, Journal of Combinatorial Theory, Series A 113 (2006), 67–83.

    Article  MathSciNet  Google Scholar 

  21. M. Hrušàk: Combinatorics of filters and ideals, Set theory and its applications 533, Contemp. Math., Amer. Math. Soc, Providence, RI (2011), 29–69.

    Article  MathSciNet  Google Scholar 

  22. P. Komjáth and V. Totik: Problems and theorems in classical set theory, Springer Science & Business Media (2006).

    MATH  Google Scholar 

  23. J. Komlós, G. Sárközy and E. Szemerédi: Blow-up lemma, Combinatorica 17 (1997), 109–123.

    Article  MathSciNet  Google Scholar 

  24. J. Komlós and M. Simonovits: Szemerédi’s regularity lemma and its applications in graph theory, Bolyai Society Mathematical Studies 2, Combinatorics, Paul Erdős is Eighty (Vol. 2), Budapest (1996), 295–352.

    Google Scholar 

  25. D. Kühn and D. Osthus: Embedding large subgraphs into dense graphs, arXiv:0901.3541, (2009).

    Book  Google Scholar 

  26. M. Las Vergnas: Sur l’existence des cycles hamiltoniens dans un graphe, CR Acad, Sci. Paris, Sér. A 270 (1970), 1361–1364.

    MathSciNet  MATH  Google Scholar 

  27. S. Letzter: Path Ramsey number for random graphs, Combinatorics, Probability and Computing 25 (2016), 612–622.

    Article  MathSciNet  Google Scholar 

  28. A. R. D. Mathias: Happy families, Ann. Math. Logic 12 (1977), 59–111.

    Article  MathSciNet  Google Scholar 

  29. A. Pokrovskiy: Partitioning edge-coloured complete graphs into monochromatic cycles and paths, Journal of Combinatorial Theory, Series B 106 (2014), 70–97.

    Article  MathSciNet  Google Scholar 

  30. R. Rado: Monochromatic paths in graphs, Ann. Discrete Math 3 (1978), 191–194.

    Article  MathSciNet  Google Scholar 

  31. F. P. Ramsey: On a problem of formal logic, Proc. London Math. Soc., 2nd Ser. 30 (1930), 264–286.

    Article  MathSciNet  Google Scholar 

  32. H. Raynaud: Sur le circuit hamiltonien bi-coloré dans les graphes orientés, Periodica Mathematica Hungarica 3 (1973), 289–297.

    Article  MathSciNet  Google Scholar 

  33. E. Szemerédi: Regular Partitions of Graphs, Colloques Internationaux C.N.R.S -Problèmes Combinatoires et Théorie des Graphes 260 (1976), 399–401.

    MathSciNet  Google Scholar 

  34. Z. Tuza: Ryser’s conjecture on transversals of r-partite hypergraphs, Ars Combinatoria 16 (1983), 201–209.

    MathSciNet  MATH  Google Scholar 

  35. E. L. Wimmers: The Shelah P-point independence theorem, Israel Journal of Mathematics 43 (1982), 28–48.

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

We thank the referees for their detailed reports, especially for providing a simplification of our original proof of Theorem 1.12.

Author information

Authors and Affiliations

  1. Department of Mathematics, Miami University, Miami, USA

    Louis DeBiasio & Paul McKenney

Authors
  1. Louis DeBiasio
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Paul McKenney
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Louis DeBiasio or Paul McKenney.

Additional information

Research supported in part by Simons Foundation Collaboration Grant # 283194.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

DeBiasio, L., McKenney, P. Density of Monochromatic Infinite Subgraphs. Combinatorica 39, 847–878 (2019). https://doi.org/10.1007/s00493-018-3724-2

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00493-018-3724-2

Mathematics Subject Classification (2010)

Search

Navigation