article

The Ramsey number for hypergraph cycles I

Authors:

Y. Peng,

J. SkokanAuthors Info & Claims

Journal of Combinatorial Theory Series A, Volume 113, Issue 1

Pages 67 - 83

https://doi.org/10.1016/j.jcta.2005.02.005

Published: 01 January 2006 Publication History

Abstract

Let C_n denote the 3-uniform hypergraph loose cycle, that is the hypergraph with vertices v₁....,v_n and edges v₁v₂v₃, v₃v₄v₅, v₅v₆v₇,....,v_n-1v_nv₁. We prove that every red-blue colouring of the edges of the complete 3-uniform hypergraph with N vertices contains a monochromatic copy of C_n, where N is asymptotically equal to 5n/4. Moreover this result is (asymptotically) best possible.

References

[1]

{1} J.A. Bondy, P. Erdös, Ramsey numbers for cycles in graphs, J. Combin. Theory Ser. B 14 (1973) 46-54.

Crossref

Google Scholar

[2]

{2} F. Chung, Regularity lemmas for hypergraphs and quasi-randomness, Random Structures Algorithms 2 (1991) 241-252.

Crossref

Google Scholar

[3]

{3} R. Faudree, R. Schelp, All Ramsey numbers for cycles in graphs, Discrete Math. 8 (1974) 313-329.

Digital Library

Google Scholar

[4]

{4} A. Figaj, T. Łuczak, The Ramsey number for a triple of long even cycles, submitted for publication.

Google Scholar

[5]

{5} P. Frankl, V. Rödl, The uniformity lemma for hypergraphs, Graphs Combin. 8 (1992) 309-312.

Digital Library

Google Scholar

[6]

{6} P. Frankl, V. Rödl, Extremal problems on set systems, Random Structures Algorithms 20 (2002) 131-164.

Digital Library

Google Scholar

[7]

{7} R Haxell, T. Łuczak, Y. Peng, V. Rödl, A. Rucińiski, M. Simonovits, J. Skokan, The Ramsey number for hypergraph cycles II, manuscript.

Google Scholar

[8]

{8} T. Łuczak, R(C_n , C_n , C_n ) ≤ (4 + 0(1))n, J. Combin. Theory Ser. B 75 (1999) 174-187.

Digital Library

Google Scholar

[9]

{9} H.J. Prömel, A. Steger, Excluding induced subgraphs Ill. A general asymptotic, Random Structures Algorithms 3 (1992) 19-31.

Digital Library

Google Scholar

[10]

{10} V. Rosta, On a Ramsey-type problem of J.A. Bondy and R Erdös, I and II, J. Combin. Theory Ser. B 15 (1973) 94-104, 105-120.

Crossref

Google Scholar

[11]

{11} E. Szemerédi, Regular partitions of graphs, in: Problèmes Combinatoires et Théorie des Graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), Colloq. Internat. CNRS n. 260, CNRS, Paris, 1978, pp. 399-401.

Google Scholar

Cited By

View all

Liu GLiu X(2022)Hamiltonian Paths and Cycles in Some 4-Uniform HypergraphsGraphs and Combinatorics10.1007/s00373-022-02524-938:4Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1007/s00373-022-02524-9
Shahsiah M(2022)Ramsey Numbers of 5-Uniform Loose CyclesGraphs and Combinatorics10.1007/s00373-021-02405-738:1Online publication date: 1-Feb-2022
https://dl.acm.org/doi/10.1007/s00373-021-02405-7
DeBiasio LMcKenney P(2019)Density of Monochromatic Infinite SubgraphsCombinatorica10.1007/s00493-018-3724-239:4(847-878)Online publication date: 1-Aug-2019
https://dl.acm.org/doi/10.1007/s00493-018-3724-2
Show More Cited By

Index Terms

The Ramsey number for hypergraph cycles I
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

The 3-colored Ramsey number of even cycles

Denote by R(L,L,L) the minimum integer N such that any 3-coloring of the edges of the complete graph on N vertices contains a monochromatic copy of a graph L. Bondy and Erdos conjectured that when L is the cycle C"n on n vertices, R(C"n,C"n,C"n)=4n-3 ...
A multipartite Ramsey number for odd cycles

In this article we study multipartite Ramsey numbers for odd cycles. Our main result is the proof that a conjecture of Gyárfás et al. (J Graph Theory 61 (2009), 12–21), holds for graphs with a large enough number of vertices. Precisely, there exists n₀ ...
Vertex arboricity of planar graphs without chordal 6-cycles

The vertex arboricity <italic>va</italic><italic>G</italic> of a graph <italic>G</italic> is the minimum number of colours the vertices can be coloured so that each colour class induces a forest. It was known that <italic>va</italic><italic>G</italic>≤3 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Combinatorial Theory Series A

Journal of Combinatorial Theory Series A Volume 113, Issue 1

January 2006

187 pages

ISSN:0097-3165

Issue’s Table of Contents

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 January 2006

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Liu GLiu X(2022)Hamiltonian Paths and Cycles in Some 4-Uniform HypergraphsGraphs and Combinatorics10.1007/s00373-022-02524-938:4Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1007/s00373-022-02524-9
Shahsiah M(2022)Ramsey Numbers of 5-Uniform Loose CyclesGraphs and Combinatorics10.1007/s00373-021-02405-738:1Online publication date: 1-Feb-2022
https://dl.acm.org/doi/10.1007/s00373-021-02405-7
DeBiasio LMcKenney P(2019)Density of Monochromatic Infinite SubgraphsCombinatorica10.1007/s00493-018-3724-239:4(847-878)Online publication date: 1-Aug-2019
https://dl.acm.org/doi/10.1007/s00493-018-3724-2
Maherani LOmidi G(2017)Monochromatic Hamiltonian Berge-cycles in colored hypergraphsDiscrete Mathematics10.1016/j.disc.2016.09.032340:8(2043-2052)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1016/j.disc.2016.09.032
Omidi GShahsiah M(2017)Ramsey numbers of uniform loose paths and cyclesDiscrete Mathematics10.1016/j.disc.2016.09.024340:6(1426-1434)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1016/j.disc.2016.09.024
Omidi GShahsiah M(2017)Ramsey numbers of 4-uniform loose cyclesDiscrete Applied Mathematics10.1016/j.dam.2017.04.046230:C(112-120)Online publication date: 30-Oct-2017
https://dl.acm.org/doi/10.1016/j.dam.2017.04.046
Peng X(2016)The Ramsey number of generalized loose paths in hypergraphsDiscrete Mathematics10.1016/j.disc.2015.09.023339:2(539-546)Online publication date: 6-Feb-2016
https://dl.acm.org/doi/10.1016/j.disc.2015.09.023
Mota GSárközy GSchacht MTaraz A(2015)Ramsey numbers for bipartite graphs with small bandwidthEuropean Journal of Combinatorics10.1016/j.ejc.2015.02.01848:C(165-176)Online publication date: 1-Aug-2015
https://dl.acm.org/doi/10.1016/j.ejc.2015.02.018
GyÁrfÁs ASÁrkÖzy G(2011)The 3-colour ramsey number of a 3-uniform berge cycleCombinatorics, Probability and Computing10.1017/S096354831000020920:1(53-71)Online publication date: 1-Jan-2011
https://dl.acm.org/doi/10.1017/S0963548310000209
Haxell PŁuczak TPeng YRÖdl VRuciŃski ASkokan J(2009)The ramsey number for 3-uniform tight hypergraph cyclesCombinatorics, Probability and Computing10.1017/S096354830800967X18:1-2(165-203)Online publication date: 1-Mar-2009
https://dl.acm.org/doi/10.1017/S096354830800967X
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

The 3-colored Ramsey number of even cycles

A multipartite Ramsey number for odd cycles

Vertex arboricity of planar graphs without chordal 6-cycles

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations