Non-Three-Colourable Common Graphs Exist

被引：32

作者：

Hatami, Hamed ^{[1
]}

Hladky, Jan ^{[2
,3
]}

Kral, Daniel ^{[4
]}

Norine, Serguei ^{[5
]}

Razborov, Alexander ^{[6
]}

机构：

[1] McGill Univ, Sch Comp Sci, Montreal, PQ, Canada

[2] Charles Univ Prague, Fac Math & Phys, Dept Appl Math, Prague 11800, Czech Republic

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

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

[5] Princeton Univ, Dept Math, Princeton, NJ 08544 USA

[6] Univ Chicago, Dept Comp Sci, Chicago, IL 60637 USA

来源：

COMBINATORICS PROBABILITY & COMPUTING | 2012年 / 21卷 / 05期

基金：

加拿大自然科学与工程研究理事会; 欧洲研究理事会; 俄罗斯基础研究基金会; 英国工程与自然科学研究理事会;

关键词：

D O I：

10.1017/S0963548312000107

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A graph H is called common if the sum of the number of copies of H in a graph G and the number in the complement of G is asymptotically minimized by taking G to be a random graph. Extending a conjecture of Erdos, Burr and Rosta conjectured that every graph is common. Thomason disproved both conjectures by showing that K-4 is not common. It is now known that in fact the common graphs are very rare. Answering a question of Sidorenko and of Jagger, St' ovicek and Thomason from 1996 we show that the 5-wheel is common. This provides the first example of a common graph that is not three-colourable.

引用

页码：734 / 742

页数：9

共 20 条

[1] Hypergraphs Do Jump
Baber, Rahil
Talbot, John
[J]. COMBINATORICS PROBABILITY & COMPUTING, 2011, 20 (02) : 161 - 171
[2] QUASI-RANDOM GRAPHS
CHUNG, FRK
GRAHAM, RL
WILSON, RM
[J]. COMBINATORICA, 1989, 9 (04) : 345 - 362
[3] An Approximate Version of Sidorenko's Conjecture
Conlon, David
Fox, Jacob
Sudakov, Benny
[J]. GEOMETRIC AND FUNCTIONAL ANALYSIS, 2010, 20 (06) : 1354 - 1366
[4] Cummings J, 2011, J COMB, V2, P1
[5] Erdos P, 1962, MAGYAR TUD AKAD MAT, V7, P459
[6] Erdos P., 1984, PROGR GRAPH THEORY, P203
[7] Goodman A W., 1959, The American Mathematical Monthly, V66, P778, DOI 10.1080/00029890.1959.11989408
[8] Grzesik A., 2011, ARXIV11020962
[9] Hatami H., 2011, ARXIV11021634
[10] Graph norms and Sidorenko's conjecture
Hatami, Hamed
[J]. ISRAEL JOURNAL OF MATHEMATICS, 2010, 175 (01) : 125 - 150

← 1 2 →