کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4655325 1632950 2014 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
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,…,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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series A - Volume 121, January 2014, Pages 64–73
نویسندگان
, ,