Hostname: page-component-74656f9884-rdgjk Total loading time: 0 Render date: 2026-11-08T09:34:41.909Z Has data issue: false hasContentIssue false
  • English
  • Français

The Ramsey Number for 3-Uniform Tight Hypergraph Cycles

Published online by Cambridge University Press:  01 March 2009

P. E. HAXELL ,
T. ŁUCZAK ,
Y. PENG ,
V. RÖDL ,
A. RUCIŃSKI  and
J. SKOKAN
P. E. HAXELL
Affiliation:
Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, CanadaN2L 3G1 (e-mail: pehaxell@math.uwaterloo.ca)
T. ŁUCZAK
Affiliation:
Department of Discrete Mathematics, Adam Mickiewicz University, 61-614 Poznań, Poland (e-mail: tomasz@amu.edu.pl, andrzej@mathcs.emory.edu)
Y. PENG
Affiliation:
Department of Mathematics and Computer Science, Indiana State University, Terre Haute, IN 47809, USA (e-mail: mapeng@isugw.indstate.edu)
V. RÖDL
Affiliation:
Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30032, USA (e-mail: rodl@mathcs.emory.edu)
A. RUCIŃSKI
Affiliation:
Department of Discrete Mathematics, Adam Mickiewicz University, 61-614 Poznań, Poland (e-mail: tomasz@amu.edu.pl, andrzej@mathcs.emory.edu)
J. SKOKAN
Affiliation:
Department of Mathematics, London School of Economics and Political Science, Houghton Street, London WC2A 2AE, UK (e-mail: jozef@member.ams.org)
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.

Let C(3)n denote the 3-uniform tight cycle, that is, the hypergraph with vertices v1, .–.–., vn and edges v1v2v3, v2v3v4, .–.–., vn−1vnv1, vnv1v2. We prove that the smallest integer N = N(n) for which every red–blue colouring of the edges of the complete 3-uniform hypergraph with N vertices contains a monochromatic copy of C(3)n is asymptotically equal to 4n/3 if n is divisible by 3, and 2n otherwise. The proof uses the regularity lemma for hypergraphs of Frankl and Rödl.

References

[1]Bondy, J. A. and Erdős, P. (1973) Ramsey numbers for cycles in graphs. J. Combin. Theory Ser. B 14 46–54.CrossRefGoogle Scholar
[2]Conlon, D., Fox, J. and Sudakov, B. Ramsey numbers of sparse hypergraphs. Random Struct. Algorithms, to appear.Google Scholar
[3]Cooley, O., Fountoulakis, N., Kühn, D. and Osthus, D. (2008) 3-uniform hypergraphs of bounded degree have linear Ramsey numbers. J. Combin. Theory Ser. B 98 484–505.CrossRefGoogle Scholar
[4]Cooley, O., Fountoulakis, N., Kühn, D. and Osthus, D. Embeddings and Ramsey numbers of sparse k-uniform hypergraphs. Combinatorica, to appear.Google Scholar
[5]Faudree, R. and Schelp, R. (1974) All Ramsey numbers for cycles in graphs. Discrete Math. 8 313–329.CrossRefGoogle Scholar
[6]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
[7]Frankl, P. and Rödl, V. (2002) Extremal problems on set systems. Random Struct. Algorithms 20 131–164.CrossRefGoogle Scholar
[8]Gyárfás, A., Sárközy, G. and Szemerédi, E. (2008) The Ramsey number of diamond-matchings and loose cycles in hypergraphs. Electron. J. Combin. 15 #R126.CrossRefGoogle Scholar
[9]Gyárfás, A., Sárközy, G. and Szemerédi, E. Long monochromatic Berge cycles in colored 4-uniform hypergraphs. Submitted.Google Scholar
[10]Gyárfás, A., Sárközy, G. and Szemerédi, E. Monochromatic Hamiltonian 3-tight Berge cycles in 2-colored 4-uniform hypergraphs. Submitted.Google Scholar
[11]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
[12]Haxell, P., Łuczak, T., Peng, Y., Rödl, V., Ruciński, A. and Skokan, J. (2007) The Ramsey number for hypergraph cycles II. CDAM Research Report LSE-CDAM-2007-04.Google Scholar
[13]Łuczak, T. (1999) R(C n, C n, C n) ≤ (4 + o(1))n. J. Combin. Theory Ser. B 75 174–187.CrossRefGoogle Scholar
[14]Nagle, B., Olsen, S., Rödl, V. and Schacht, M. (2008) On the Ramsey number of sparse 3-graphs. Graphs Combin. 24 205–228.CrossRefGoogle Scholar
[15]Polcyn, J., Rödl, V., Ruciński, A. and Szemerédi, E. (2006) Short paths in quasi-random triple systems with sparse underlying graphs. J. Combin. Theory Ser. B 96 584–607.CrossRefGoogle Scholar
[16]Radziszowski, S. P. (1994) Small Ramsey numbers. Electronic J. Combin. 1, Dynamic Survey 1, 30 pp.Google Scholar
[17]Rödl, V., Ruciński, A. and Szemerédi, E. (2006) A Dirac-type theorem for 3-uniform hypergraphs. Combin. Probab. Comput. 15 253–279.CrossRefGoogle Scholar
[18]Rosta, V. (1973) On a Ramsey-type problem of J. A. Bondy and P. Erdős, I and II. J. Combin. Theory Ser. B 15 94–104, 105–120.CrossRefGoogle Scholar
[19]Szemerédi, E. (1978) Regular partitions of graphs. In Problèmes Combinatoires et Théorie des Graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), Vol. 260 of Colloq. Internat. CNRS, CNRS, Paris, pp. 399–401.Google Scholar