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 条

[11] Greenwood R. E., 1955, Canad. J. Math., V7, P1, DOI DOI 10.4153/CJM-1955-001-4
[12] Non-Three-Colourable Common Graphs Exist
Hatami, Hamed
Hladky, Jan
Kral, Daniel
Norine, Serguei
Razborov, Alexander
[J]. COMBINATORICS PROBABILITY & COMPUTING, 2012, 21 (05) : 734 - 742
[13] Multiplicities of subgraphs
Jagger, C
Stovicek, P
Thomason, A
[J]. COMBINATORICA, 1996, 16 (01) : 123 - 141
[14] JANSON S, 2000, WIL INT S D, pR5, DOI 10.1002/9781118032718
[15] Pikhurko O., 2012, COMMUNICATION
[16] On a problem of formal logic
Ramsey, FP
[J]. PROCEEDINGS OF THE LONDON MATHEMATICAL SOCIETY, 1930, 30 : 264 - 286
[17] Flag algebras
Razborov, Alexander A.
[J]. JOURNAL OF SYMBOLIC LOGIC, 2007, 72 (04) : 1239 - 1282
[18] ON 3-HYPERGRAPHS WITH FORBIDDEN 4-VERTEX CONFIGURATIONS
Razborov, Alexander A.
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2010, 24 (03) : 946 - 963
[19] MONOCHROMATIC TRIANGLES IN 3 COLORS
SANE, SS
WALLIS, WD
[J]. BULLETIN OF THE AUSTRALIAN MATHEMATICAL SOCIETY, 1988, 37 (02) : 197 - 212
[20] THOMASON A, 1989, J LOND MATH SOC, V39, P246

← 1 2 3 →