Monochromatic triangles in three-coloured graphs

被引：22

作者：

Cummings, James ^{[1
]}

Kral, Daniel ^{[2
,3
,8
]}

Pfender, Florian ^{[4
]}

Sperfeld, Konrad ^{[5
]}

Treglown, Andrew ^{[6
,8
]}

Young, Michael ^{[7
]}

机构：

[1] Carnegie Mellon Univ, Dept Math Sci, Pittsburgh, PA 15213 USA

[2] Univ Warwick, Math Inst, DIMAP, Coventry CV4 7AL, W Midlands, England

[3] Univ Warwick, Dept Comp Sci, Coventry CV4 7AL, W Midlands, England

[4] Univ Colorado, Denver, CO 80202 USA

[5] Univ Rostock, Inst Math, D-18057 Rostock, Germany

[6] Univ London, Sch Math Sci, London E1 4NS, England

[7] Iowa State Univ, Dept Math, Ames, IA 50011 USA

[8] Charles Univ Prague, Fac Math & Phys, Inst Comp Sci, Prague 11800, Czech Republic

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2013年 / 103卷 / 04期

基金：

美国国家科学基金会; 欧洲研究理事会;

关键词：

Triangle density; Flag algebra; Extremal graph; RAMSEY MULTIPLICITY;

D O I：

10.1016/j.jctb.2013.05.002

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In 1959, Goodman [9] determined the minimum number of monochromatic triangles in a complete graph whose edge set is 2-coloured. Goodman (1985) [10] also raised the question of proving analogous results for complete graphs whose edge sets are coloured with more than two colours. In this paper, for n sufficiently large, we determine the minimum number of monochromatic triangles in a 3-coloured copy of K-n. Moreover, we characterise those 3-coloured copies of K-n that contain the minimum number of monochromatic triangles. (C) 2013 Elsevier Inc. All rights reserved.

引用

页码：489 / 503

页数：15

共 23 条

[1] CSDP, a C library for semidefinite programming
Borchers, B
[J]. OPTIMIZATION METHODS & SOFTWARE, 1999, 11-2 (1-4) : 613 - 623
[2] ON THE RAMSEY MULTIPLICITIES OF GRAPHS - PROBLEMS AND RECENT RESULTS
BURR, SA
ROSTA, V
[J]. JOURNAL OF GRAPH THEORY, 1980, 4 (04) : 347 - 361
[3] On the Ramsey multiplicity of complete graphs
Conlon, David
[J]. COMBINATORICA, 2012, 32 (02) : 171 - 186
[4] Cummings J., ARXIV12061987V1
[5] Cummings J, 2011, J COMB, V2, P1
[6] Erdos P, 1962, MAGYAR TUD AKAD MAT, V7, P459
[7] There exist graphs with super-exponential Ramsey multiplicity constant
Fox, Jacob
[J]. JOURNAL OF GRAPH THEORY, 2008, 57 (02) : 89 - 98
[8] Giraud G., 1976, DISCRETE MATH, V16, P13
[9] Goodman A W., 1959, The American Mathematical Monthly, V66, P778, DOI 10.1080/00029890.1959.11989408
[10] TRIANGLES IN A COMPLETE CHROMATIC GRAPH WITH 3 COLORS
GOODMAN, AW
[J]. DISCRETE MATHEMATICS, 1985, 57 (03) : 225 - 235

← 1 2 3 →