Hostname: page-component-6898cfcb55-zkb6p Total loading time: 0 Render date: 2026-11-11T18:40:09.079Z Has data issue: false hasContentIssue false
  • English
  • Français

The 3-Colour Ramsey Number of a 3-Uniform Berge Cycle

Published online by Cambridge University Press:  02 July 2010

ANDRÁS GYÁRFÁS and
GÁBOR N. SÁRKÖZY
ANDRÁS GYÁRFÁS
Affiliation:
Computer and Automation Research Institute, Hungarian Academy of Sciences, Budapest, PO Box 63, Budapest, Hungary, H-1518 (e-mail: gyarfas@sztaki.hu)
GÁBOR N. SÁRKÖZY
Affiliation:
Computer and Automation Research Institute, Hungarian Academy of Sciences, Budapest, PO Box 63, Budapest, Hungary, H-1518 (e-mail: gyarfas@sztaki.hu)Computer Science Department, Worcester Polytechnic Institute, Worcester, MA 01609, USA (e-mail: gsarkozy@cs.wpi.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

The asymptotics of 2-colour Ramsey numbers of loose and tight cycles in 3-uniform hypergraphs were recently determined [16, 17]. We address the same problem for Berge cycles and for 3 colours. Our main result is that the 3-colour Ramsey number of a 3-uniform Berge cycle of length n is asymptotic to $\frac{5n}{4}$. The result is proved with the Regularity Lemma via the existence of a monochromatic connected matching covering asymptotically 4n/5 vertices in the multicoloured 2-shadow graph induced by the colouring of Kn(3).

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 20 , Issue 1 , January 2011, pp. 53 - 71
Copyright
Copyright © Cambridge University Press 2010

References

[1]Berge, C. (1973) Graphs and Hypergraphs, North-Holland.Google Scholar
[2]Bermond, J. C., Germa, A., Heydemann, M. C. and Sotteau, D. (1978) Hypergraphes hamiltoniens. In Problèmes Combinatoires et Tháorie des Graphes (Colloq. Internat. CNRS, Orsay 1976), Vol. 260, pp. 39–43.Google Scholar
[3]Chung, F. (1991) Regularity lemmas for hypergraphs and quasi-randomness. Random Struct. Alg. 2 241–252.CrossRefGoogle Scholar
[4]Erdős, P. and Gallai, T. (1959) On maximal paths and circuits of graphs. Acta Math. Acad. Sci. Hungar. 10 337–356.CrossRefGoogle Scholar
[5]Figaj, A. and Łuczak, T. (2007) The Ramsey number for a triple of long even cycles. J. Combin. Theory Ser. B 97 584–596.CrossRefGoogle Scholar
[6]Frankl, P. and Rödl, V. (1992) The uniformity lemma for hypergraphs. Graphs Combin. 8 309–312.CrossRefGoogle Scholar
[7]Füredi, Z. and Gyárfás, A. (1991) Covering t-element sets by partitions. Europ. J. Combin. 12 483–489.CrossRefGoogle Scholar
[8]Gerencsár, L. and Gyárfás, A. (1967) On Ramsey-type problems. Ann. Univ. Sci. Budapest Eötvös, Sect. Math. 10 167–170.Google Scholar
[9]Gowers, W. T. (2007) Hypergraph regularity and the multidimensional Szemerádi Theorem. Ann. of Math. (2) 166 897–946.CrossRefGoogle Scholar
[10]Gyárfás, A. (1973) Partition coverings and blocking sets of hypergraphs (in Hungarian). Studies of Computer and Automation Research Institute, No. 71, MR0357172.Google Scholar
[11]Gyárfás, A., Lehel, J., Sárközy, G. N. and Schelp, R. H. (2008) Monochromatic Hamiltonian Berge cycles in colored complete hypergraphs. J. Combin. Theory Ser. B 98 342–358.CrossRefGoogle Scholar
[12]Gyárfás, A., Ruszinkó, M., Sárközy, G. N. and Szemerádi, E. (2006) An improved bound for the monochromatic cycle partition number. J. Combin. Theory Ser. B 96 855–873.CrossRefGoogle Scholar
[13]Gyárfás, A., Ruszinkó, M., Sárközy, G. N. and Szemerádi, E. (2006) One-sided coverings of colored complete bipartite graphs. In Topics in Discrete Mathematics (dedicated to J. Nešetřil on his 60th birthday), Vol. 26 of Algorithms and Combinatorics (Klazar, M. et al. , eds), Springer, pp. 133–154.CrossRefGoogle Scholar
[14]Gyárfás, A., Ruszinkó, M., Sárközy, G. N. and Szemerádi, E. (2007) Three-color Ramsey numbers for paths. Combinatorica 27 35–69.CrossRefGoogle Scholar
[15]Gyárfás, A., Ruszinkó, M., Sárközy, G. N. and Szemerádi, E. (2007) Tripartite Ramsey numbers for paths. J. Graph Theory 55 164–174.CrossRefGoogle Scholar
[16]Haxell, P., Łuczak, T., Peng, Y., Rödl, V., Ruciński, A., Simonovits, M. and Skokan, J. (2006) The Ramsey number for hypergraph cycles I. J. Combin. Theory Ser. A 113 67–83.CrossRefGoogle Scholar
[17]Haxell, P., Łuczak, T., Peng, Y., Rödl, V., Ruciński, A. and Skokan, J. (2009) The Ramsey number for 3-uniform tight hypergraph cycles. Combin. Probab. Comput. 18 165–203.CrossRefGoogle Scholar
[18]Katona, G. Y. and Kierstead, H. A. (1999) Hamiltonian chains in hypergraphs. J. Graph Theory 30 205–212.3.0.CO;2-O>CrossRefGoogle Scholar
[19]Kohayakawa, Y., Simonovits, M. and Skokan, J. The 3-color Ramsey number of odd cycles. Manuscript. J. Combin. Theory Ser. B, to appear.Google Scholar
[20]Komlós, J., Sárközy, G. N. and Szemerádi, E. (1997) Blow-Up Lemma. Combinatorica 17 109–123.CrossRefGoogle Scholar
[21]Komlós, J., Sárközy, G. N. and Szemerádi, E. (1998) An algorithmic version of the Blow-Up Lemma. Random Struct. Alg. 12 297–312.3.0.CO;2-Q>CrossRefGoogle Scholar
[22]Komlós, J. and Simonovits, M. (1996) Szemerádi's Regularity Lemma and its applications in graph theory. In Combinatorics: Paul Erdős is Eighty (Miklós, D., Sós, V. T., and Szőnyi, T., eds), Vol. 2 of Bolyai Society Math. Studies, pp. 295–352.Google Scholar
[23]Lovász, L. and Plummer, M. D. (1986) Matching Theory, North-Holland and Akadámiai Kiadó.Google Scholar
[24]Łuczak, T. (1999) R(Cn, Cn, Cn) ≤ (4 + o(1))n. J. Combin. Theory Ser. B 75 174–187.CrossRefGoogle Scholar
[25]Rosta, V. (1973) On a Ramsey-type problem of J. A. Bondy and P. Erdős I. J. Combin. Theory Ser. B 15 94–104.CrossRefGoogle Scholar
[26]Rosta, V. (1973) On a Ramsey-type problem of J. A. Bondy and P. Erdős II. J. Combin. Theory Ser. B 15 105–120.CrossRefGoogle Scholar
[27]Rödl, V., Ruciński, A. and Szemerádi, E. (2006) A Dirac-type theorem for 3-uniform hypergraphs. Combin. Probab. Comput. 15 229–251.CrossRefGoogle Scholar
[28]Rödl, V. and Skokan, J. (2004) Regularity Lemma for uniform hypergraphs. Random Struct. Alg. 25 1–42.CrossRefGoogle Scholar
[29]Szemerádi, E. (1978) Regular partitions of graphs. In In Problèmes Combinatoires et Tháorie des Graphes (Colloq. Internat. CNRS, Orsay 1976), Vol. 260, pp. 399–401.Google Scholar
[30]Tao, T. (2006) A variant of the hypergraph removal lemma. J. Combin. Theory Ser. A 113 1257–1280.CrossRefGoogle Scholar