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

Three-Color Ramsey Number of an Odd Cycle Versus Bipartite Graphs with Small Bandwidth

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

A graph \(\mathcal {H}=(W,E_\mathcal {H})\) is said to have bandwidth at most b if there exists a labeling of W as \(w_1,w_2,\dots ,w_n\) such that \(|i-j|\le b\) for every edge \(w_iw_j\in E_\mathcal {H}\). We say that \(\mathcal {H}\) is a balanced \((\beta ,\Delta )\)-graph if it is a bipartite graph with bandwidth at most \(\beta |W|\) and maximum degree at most \(\Delta \), and it also has a proper 2-coloring \(\chi :W\rightarrow [2]\) such that \(||\chi ^{-1}(1)|-|\chi ^{-1}(2)||\le \beta |\chi ^{-1}(2)|\). In this paper, we prove that for every \(\gamma >0\) and every natural number \(\Delta \), there exists a constant \(\beta >0\) such that for every balanced \((\beta ,\Delta )\)-graph \(\mathcal {H}\) on n vertices we have

$$\begin{aligned}R(\mathcal {H}, \mathcal {H}, C_n) \le (3+\gamma )n\end{aligned}$$

for all sufficiently large odd n. The upper bound is sharp for several classes of graphs. Let \(\theta _{n,t}\) be the graph consisting of t internally disjoint paths of length n all sharing the same endpoints. As a corollary, for each fixed \(t\ge 1\), \(R(\theta _{n, t},\theta _{n, t}, C_{nt+\lambda })=(3t+o(1))n,\) where \(\lambda =0\) if nt is odd and \(\lambda =1\) if nt is even. In particular, we have \(R(C_{2n},C_{2n}, C_{2n+1})=(6+o(1))n\), which is a special case of a result of Figaj and Łuczak (2018).

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

Data Availibility Statement

Data sharing not applicable to this article as no datasets were generated or analysed during the current study.

References

  1. Allen, P., Brightwell, G., Skokan, J.: Ramsey-goodness and otherwise. Combinatorica 33, 125–160 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  2. Alon, N., Fox, J., Zhao, Y.: Efficient arithmetic regularity and removal lemmas for induced bipartite patterns. Discrete Anal. Paper No. 3, p. 14 (2019)

  3. Balogh, J., Kostochka, A., Lavrov, M., Liu, X.: Monochromatic paths and cycles in \(2\)-edge-colored graphs with large minimum degree. arXiv:1906.02854

  4. Benevides, F.S., Skokan, J.: The 3-colored Ramsey number of even cycles. J. Combin. Theory Ser. B 99, 690–708 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  5. Benevides, F.S., Luczak, T., Scott, A., Skokan, J., White, M.: Monochromatic cycles in 2-coloured graphs. Combin. Probab. Comput. 21, 57–87 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  6. Bielak, H.: Multicolor Ramsey numbers for some paths and cycles. Discuss. Math. Graph Theory 29, 209–218 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  7. Bondy, J.A., Erdős, P.: Ramsey numbers for cycles in graphs. J. Combin. Theory Ser. B 14, 46–54 (1973)

    Article  MathSciNet  MATH  Google Scholar 

  8. Böttcher, J.: Embedding large graphs–The Bollobás-Komlós conjecture and beyond. Ph.D. thesis, Technischen Universität München (2009)

  9. Böttcher, J., Pruessmann, K.P., Taraz, A., Würfl, A.: Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs. Eur. J. Combin. 31, 1217–1227 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  10. Böttcher, J., Heinig, P., Taraz, A.: Embedding into bipartite graphs. SIAM J. Discrete Math. 24, 1215–1233 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  11. Chen, X., Lin, Q., You, C.: Ramsey numbers of large books. J. Graph Theory 101(1), 124–133 (2022)

  12. Conlon, D., Fox, J., Wigderson, Y.: Ramsey number of books and quasirandomness. Combinatorica 42(1), 309–363 (2022)

  13. Conlon, D.: The Ramsey number of books. Adv. Combin. 3, 12 (2019)

    MathSciNet  MATH  Google Scholar 

  14. Conlon, D., Fox, J.: Bounds for graph regularity and removal lemmas. Geom. Funct. Anal. 22, 1191–1256 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  15. Dzido, T., Fidytek, R.: On some three color Ramsey numbers for paths and cycles. Discrete Math. 309, 4955–4958 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  16. Erdős, P., Gallai, T.: On maximal paths and circuits of graphs. Acta Math. Hungar. 10, 337–356 (1959)

    Article  MathSciNet  MATH  Google Scholar 

  17. Erdős, P., Faudree, R.J., Rousseau, C.C., Schelp, R.H.: Generalized Ramsey theory for multiple colors. J. Combin. Theory Ser. B 20, 250–264 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  18. Faudree, R.J., Schelp, R.H.: All Ramsey numbers for cycles in graphs. Discrete Math. 8, 313–329 (1974)

    Article  MathSciNet  MATH  Google Scholar 

  19. Faudree, R.J., Schelp, R.H.: Path Ramsey numbers in multicolorings. J. Combin. Theory Ser. B 19, 150–160 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  20. Faudree, R.J., Lawrence, S.L., Parsons, T.D., Schelp, R.H.: Path-Cycle Ramsey numbers. Discrete Math. 10, 269–277 (1974)

    Article  MathSciNet  MATH  Google Scholar 

  21. Ferguson, D.G.: The Ramsey number of mixed-parity cycles I. arXiv:1508.07154

  22. Ferguson, D.G.: The Ramsey number of mixed-parity cycles II. arXiv:1508.07171

  23. Ferguson, D.G.: The Ramsey number of mixed-parity cycles III. arXiv:1508.07176

  24. Figaj, A., Łuczak, T.: The Ramsey number for a triple of long even cycles. J. Combin. Theory Ser. B 97, 584–596 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  25. Figaj, A., Łuczak, T.: The Ramsey numbers for a triple of long cycles. Combinatorica 38, 827–845 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  26. Fox, J., Lovász, L.M., Zhao, Y.: On regularity lemmas and their algorithmic applications. Combin. Probab. Comput. 26, 481–505 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  27. Gerencsér, L., Gyarfás, A.: On Ramsey-type problems. Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 10, 167–170 (1967)

    MathSciNet  MATH  Google Scholar 

  28. Gyárfás, A.: Large monochromatic components in edge colorings of graphs: a survey. In: Soifer, A. (ed.) Ramsey Theory: Yesterday, Today and Tomorrow, pp. 77–96. Birkhäuser, Basel (2010)

    Google Scholar 

  29. Gyárfás, A., Sárközy, G.N.: Star versus two stripes Ramsey numbers and a conjecture of Schelp. Combin. Probab. Comput. 21, 179–186 (2012)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  31. Jenssen, M., Skokan, J.: Exact Ramsey numbers of odd cycles via nonlinear optimisation. Adv. Math. 376, 46 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  32. Knierim, C., Su, P.: Improved bounds on the multicolor Ramsey numbers of paths and even cycles. Electron. J. Combin. 26, 1.26 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  33. Kohayakawa, Y., Simonovits, M., Skokan, J.: The 3-colored Ramsey number of odd cycles. Electron. Notes Discrete Math. 19, 397–402 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  34. Komlós, J., Simonovits, M.: Szemerédi’s regularity lemma and its applications in graph theory. Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), Bolyai Soc. Math. Stud., 2, János Bolyai Math. Soc., Budapest, pp. 295–352 (1996)

  35. Lin, Q., Peng, X.: Large book-cycle Ramsey numbers. SIAM J. Discrete Math. 35, 532–545 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  36. Łuczak, T.: \(R(C_n, C_n, C_n) \le (4 + o(1))n\). J. Combin. Theory Ser. B 75, 174–187 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  37. Łuczak, T., Simonovits, M., Skokan, J.: On the multi-colored Ramsey numbers of cycles. J. Graph Theory 69, 169–175 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  38. Mota, G., Sárközy, G.N., Schacht, M., Taraz, A.: Ramsey number for bipartite graphs with small bandwidth. Eur. J. Combin. 48, 165–176 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  39. Nikiforov, V., Rousseau, C.C.: Ramsey goodness and beyond. Combinatorica 29, 227–262 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  40. Omidi, G.R., Raeisi, G.: On multicolor Ramsey number of paths versus cycles. Electron. J. Combin. 18, 24 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  41. Rödl, V., Schacht, M.: Regularity Lemmas for Graphs. Fete of Combinatorics and Computer Science. Bolyai Soc. Math. Stud., 20, János Bolyai Math. Soc., Budapest, pp. 287–325 (2010)

  42. Rosta, V.: On a Ramsey-type problem of J. A. Bondy and P. Erdős I, II. J. Combin. Theory Ser. B 15, 105–120 (1973)

    Article  MathSciNet  MATH  Google Scholar 

  43. Sárkozy, G.N.: On the multi-colored Ramsey numbers of paths and even cycles. Electron. J. Combin. 23, 3 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  44. Schelp, R.H.: Some Ramsey-Turán type problems and related questions. Discrete Math. 312, 2158–2161 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  45. Shao, Z., Xu, X., Shi, X., Pan, L.: Some three-color Ramsey numbers, \(R(P_4, P_5, C_k)\) and \(R(P_4, P_6, C_k)\). Eur. J. Combin. 30, 396–403 (2009)

    Article  MATH  Google Scholar 

  46. Szemerédi, E.: Regular Partitions of Graphs, Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, 1976), Colloq. Internat. CNRS, 260, CNRS, Paris, pp. 399–401 (1978)

  47. Szemerédi, E.: Arithmetic progressions, different regularity lemmas and removal lemmas. Commun. Math. Stat. 3, 315–328 (2015)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Funding

This work was supported by No. 12171088. Q. Lin has received research support from NSFC.

Author information

Authors and Affiliations

  1. Center for Discrete Mathematics, Fuzhou University, Fuzhou, 350108, People’s Republic of China

    Chunlin You & Qizhong Lin

  2. School of Mathematics and Statistics, Yancheng Teachers University, Yancheng, 224002, Jiangsu, People’s Republic of China

    Chunlin You

Authors
  1. Chunlin You
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Qizhong Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

All authors contributed to the study conception and design. Material preparation, data collection and analysis were performed by Chunlin You and Qizhong Lin. The first draft of the manuscript was written by Chunlin You and all authors commented on previous versions of the manuscript. All authors read and approved the final manuscript.

Corresponding author

Correspondence to Chunlin You.

Ethics declarations

Conflict of interest

The authors have no relevant financial or non-financial interests to disclose.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Supported in part by NSFC (no. 12171088, 12226401) and NSFFJ (No. 2022J02018).

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

You, C., Lin, Q. Three-Color Ramsey Number of an Odd Cycle Versus Bipartite Graphs with Small Bandwidth. Graphs and Combinatorics 39, 46 (2023). https://doi.org/10.1007/s00373-023-02640-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s00373-023-02640-0

Keywords

Mathematics Subject Classification