Ramsey numbers of 3-uniform loose paths and loose cycles

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:121

Article

Omidi, G. R.^1,2  Shahsiah, M.¹ 

[1] Isfahan Univ Technol, Dept Math Sci, Esfahan 8415683111, Iran

[2] Sch Math, Inst Res Fundamental Sci IPM, Tehran 193955746, Iran

关键词: Ramsey number;    Uniform hypergraph;    Loose path;    Loose cycle;   

DOI  :  10.1016/j.jcta.2013.09.003

来源: Elsevier

【 摘 要 】

The 3-uniform loose cycle, denoted by C-n(3), is the hypergraph with vertices v(1), v(2), ..., v25 and n edges v(1) v(2) v(3), v(3)v(4) v(5), ..., v(2n-1) v(2n) v(1). Similarly, the 3-uniform loose path 73',? is the hypergraph with vertices v1, 1/2,. ... v25+1 and n edges v(1) v(2)v(3), v(3)v(4)v(5), v(2n-1) V2nV2n-1-1. In 2006 Haxell et al. proved that the 2-color Ramsey number of 3-uniform loose cycles on 2n vertices is asymptotically V. 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 (P-n(3), P-m(3)) = R (P-n(3),) = R(c(n)(3),c(m)(3)) +1 I m + 1 L2 t =2n+ and for every n > m >= 3, R (P-m(3), C-n(3) = 2n + Layij. This gives a positive answer to a recent question of Gyarfas and Raeisi. (C) 2013 Elsevier Inc. All rights reserved.

【 授权许可】

Free