The Ramsey Number for 3-Uniform Tight Hypergraph Cycles

被引：22

作者：

Haxell, P. E. ^{[1
]}

Luczak, T. ^{[2
]}

Peng, Y. ^{[3
]}

Roedl, V. ^{[4
]}

Rucinski, A. ^{[2
]}

Skokan, J. ^{[5
]}

机构：

[1] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada

[2] Adam Mickiewicz Univ, Dept Discrete Math, PL-61614 Poznan, Poland

[3] Indiana State Univ, Dept Math & Comp Sci, Terre Haute, IN 47809 USA

[4] Emory Univ, Dept Math & Comp Sci, Atlanta, GA 30032 USA

[5] Univ London London Sch Econ & Polit Sci, Dept Math, London WC2A 2AE, England

来源：

COMBINATORICS PROBABILITY & COMPUTING | 2009年 / 18卷 / 1-2期

基金：

巴西圣保罗研究基金会; 美国国家科学基金会;

关键词：

TRIPLE;

D O I：

10.1017/S096354830800967X

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Let C-n((3)) denote the 3-uniform tight cycle, that is, the hypergraph with vertices v(1),...,v(n) and edges v(1)v(2)v(3), v(2)v(3)v(4), ... ,v(n-1)v(n)v(1), v(n)v(1)v(2). We prove that the smallest integer N = N(n) for which every red-blue colouring of the edges of the complete 3-uniform hypergraph with N vertices contains a monochromatic copy of C-n((3)) is asymptotically equal to 4n/3 if n is divisible by 3, and 2n otherwise. The proof uses the regularity lemma for hypergraphs of Frankl and Rodl.

引用

页码：165 / 203

页数：39

共 20 条

[1]

[Anonymous], 1994, ELECTRON J COMB

[2]

Bondy J. A., 1973, J. Combinatorial Theory Ser. B, V14, P46, DOI [10.1016/s0095-8956(73)80005-x, DOI 10.1016/S0095-8956(73)80005-X]

[3]

CONLON D, RANDOM STRU IN PRESS

[4]

COOLEY O, COMBINATORI IN PRESS

[5] 3-Uniform hypergraphs of bounded degree have linear Ramsey numbers [J].

Cooley, Oliver ;

Fountoulakis, Nikolaos ;

Kuehn, Daniela ;

Osthus, Deryk .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2008, 98 (03) :484-505

[6]

Faudree R. J., 1974, Discrete Mathematics, V8, P313, DOI 10.1016/0012-365X(74)90151-4

[7] The Ramsey number for a triple of long even cycles [J].

Figaj, Agnieszka ;

Luczak, Tomasz .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2007, 97 (04) :584-596

[8] Extremal problems on set systems [J].

Frankl, P ;

Rödl, V .

RANDOM STRUCTURES & ALGORITHMS, 2002, 20 (02) :131-164

[9]

GYARFAS A, MONOCHROMATIC UNPUB

[10]

GYARFAS A, LONG MONOCHROM UNPUB

← 1 2 →