The Ramsey number for hypergraph cycles I

被引：43

作者：

Haxell, PE ^{[1
]}

Luczak, T

Peng, Y

Rödl, V

Rucinski, A

Simonovits, M

Skokan, J

机构：

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

[2] Adam Mickiewicz Univ Poznan, 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] Hungarian Acad Sci, Alfred Renyi Inst Math, H-1053 Budapest, Hungary

[6] Univ Illinois, Dept Math, Urbana, IL 61801 USA

[7] Univ Sao Paulo, Inst Matemat & Estatist, BR-05508090 Sao Paulo, Brazil

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES A | 2006年 / 113卷 / 01期

基金：

美国国家科学基金会; 加拿大自然科学与工程研究理事会;

关键词：

Ramsey number; hypergraph; colouring; regularity lemma; cycle;

D O I：

10.1016/j.jcta.2005.02.005

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let C-n denote the 3-uniform hypergraph loose cycle, that is the hypergraph with vertices v(1),...,v(n) and edges v(1)v(2)v(3), v(3)v(4)v(5), v(5)v(6)v(7),.., v(n-1)v(n)v(1). We prove that every red-blue colouring of the edges of the complete 3-uniform hypergraph with N vertices contains a monochromatic copy of C-n, where N is asymptotically equal to 5n/4. Moreover this result is (asymptotically) best possible. (c) 2005 Elsevier Inc. All rights reserved.

引用

页码：67 / 83

页数：17

共 12 条

[1]

Bondy J.A., 1973, J COMB THEORY B, V14, P46, DOI DOI 10.1016/J.JCTB.2008.12.002

[2]

CHUNG FRK, 1991, RANDOM STRUCT ALGOR, V2, P241

[3]

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

[4]

FIGAJ A, UNPUB RAMSEY NUMBER

[5] THE UNIFORMITY LEMMA FOR HYPERGRAPHS [J].

FRANKL, P ;

RODL, V .

GRAPHS AND COMBINATORICS, 1992, 8 (04) :309-312

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

Frankl, P ;

Rödl, V .

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

[7]

HAXELL P, UNPUB RAMSEY NUMBER, V2

[8] R(Cn,Cn,Cn)≤(4+o(1))n [J].

Luczak, T .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1999, 75 (02) :174-187

[9] EXCLUDING INDUCED SUBGRAPHS .3. A GENERAL ASYMPTOTIC [J].

PROMEL, HJ ;

STEGER, A .

RANDOM STRUCTURES & ALGORITHMS, 1992, 3 (01) :19-31

[10]

Rosta V., 1973, Journal of Combinatorial Theory, Series B, V15, P105, DOI 10.1016/0095-8956(73)90036-1

← 1 2 →