Stability of the path-path Ramsey number

被引：6

作者：

Gyarfas, Andras ^{[1
]}

Sarkozy, Gabor N. ^{[1
,2
]}

Szemeredi, Endre ^{[3
,4
]}

机构：

[1] Hungarian Acad Sci, Comp & Automat Res Inst, H-1518 Budapest, Hungary

[2] Worcester Polytech Inst, Dept Comp Sci, Worcester, MA 01609 USA

[3] Rutgers State Univ, Dept Comp Sci, New Brunswick, NJ 08903 USA

[4] Inst Adv Study, Princeton, NJ 08540 USA

来源：

DISCRETE MATHEMATICS | 2009年 / 309卷 / 13期

基金：

美国国家科学基金会;

关键词：

Ramsey theory; Stability; Path;

D O I：

10.1016/j.disc.2009.02.025

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Here we prove a stability version of a Ramsey-type Theorem for paths. Thus in any 2-coloring of the edges of the complete graph K. we can either find a monochromatic path substantially longer than 2n/3, or the coloring is close to the extremal coloring. (C) 2009 Elsevier B.V. All rights reserved.

引用

页码：4590 / 4595

页数：6

共 13 条

[1] BOLLOBAS B, 1976, J LOND MATH SOC, V12, P219
[2] Bollobas B., 1978, EXTREMAL GRAPH THEOR
[3] Gerencsr L., 1967, Ann. Univ. Sci. Budapest. Eotvos Sect. Math., V10, P167
[4] Graham R., 1990, RAMSEY THEORY
[5] GYARFAS A, MONOCHROMATIC UNPUB
[6] Three-color Ramsey numbers for paths
Gyarfas, Andras
Ruszinko, Miklos
Sarkozy, Gabor N.
Szemeredi, Endre
[J]. COMBINATORICA, 2007, 27 (01) : 35 - 69
[7] KOHAYAKAWA Y, 3 COLORED RAMS UNPUB
[8] Kovari T., 1954, C MATH, V3, P50
[9] LEVITT I, DISCRETE MA IN PRESS
[10] Cycles and stability
Nikiforov, V.
Schelp, R. H.
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2008, 98 (01) : 69 - 84

← 1 2 →