کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4655325 | 1632950 | 2014 | 10 صفحه PDF | دانلود رایگان |
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.
Journal: Journal of Combinatorial Theory, Series A - Volume 121, January 2014, Pages 64–73