Ramsey numbers of 3-uniform loose paths and loose cycles

The 3-uniform loose cycle, denoted by Cn3, is the hypergraph with vertices v1,v2,…,v2n and n edges v1v2v3,v3v4v5,…,v2n−1v2nv1. Similarly, the 3-uniform loose pathPn3 is the hypergraph with vertices v1,v2,…,v2n+1 and n edges v1v2v3,v3v4v5,…,v2n−1v2nv2n+1. In 2006 Haxell et al. proved that the 2-color...

Full description

Saved in:
Bibliographic Details
Published in:Journal of combinatorial theory. Series A 2014-01, Vol.121, p.64-73
Main Authors: Omidi, G.R., Shahsiah, M.
Format: Article
Language:English
Subjects:
Loose cycle
Loose path
Ramsey number
Uniform hypergraph
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The 3-uniform loose cycle, denoted by Cn3, is the hypergraph with vertices v1,v2,…,v2n and n edges v1v2v3,v3v4v5,…,v2n−1v2nv1. Similarly, the 3-uniform loose pathPn3 is the hypergraph with vertices v1,v2,…,v2n+1 and n edges v1v2v3,v3v4v5,…,v2n−1v2nv2n+1. In 2006 Haxell et al. proved that the 2-color Ramsey number of 3-uniform loose cycles on 2n vertices is asymptotically 5n2. Their proof is based on the method of the Regularity Lemma. Here, without using this method, we generalize their result by determining the exact values of 2-color Ramsey numbers involving loose paths and cycles in 3-uniform hypergraphs. More precisely, we prove that for every n⩾m⩾3,R(Pn3,Pm3)=R(Pn3,Cm3)=R(Cn3,Cm3)+1=2n+⌊m+12⌋, and for every n>m⩾3, R(Pm3,Cn3)=2n+⌊m−12⌋. This gives a positive answer to a recent question of Gyárfás and Raeisi.
ISSN:0097-3165
1096-0899
DOI:10.1016/j.jcta.2013.09.003