Article ID Journal Published Year Pages File Type
4655325 Journal of Combinatorial Theory, Series A 2014 10 Pages PDF
Abstract

The 3-uniform loose cycle  , denoted by Cn3, is the hypergraph with vertices v1,v2,…,v2nv1,v2,…,v2n and n   edges v1v2v3,v3v4v5,…,v2n−1v2nv1v1v2v3,v3v4v5,…,v2n−1v2nv1. Similarly, the 3-uniform loose path  Pn3 is the hypergraph with vertices v1,v2,…,v2n+1v1,v2,…,v2n+1 and n   edges v1v2v3,v3v4v5,…,v2n−1v2nv2n+1v1v2v3,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⩾3n⩾m⩾3,R(Pn3,Pm3)=R(Pn3,Cm3)=R(Cn3,Cm3)+1=2n+⌊m+12⌋, and for every n>m⩾3n>m⩾3, R(Pm3,Cn3)=2n+⌊m−12⌋. This gives a positive answer to a recent question of Gyárfás and Raeisi.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,