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