Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-15T19:20:42.731Z 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)
Get access Rights & Permissions [Opens in a new window]

Abstract

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

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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