Hostname: page-component-8448b6f56d-tj2md Total loading time: 0 Render date: 2024-04-17T19:54:50.789Z Has data issue: false hasContentIssue false
  • English
  • Français

Non-Three-Colourable Common Graphs Exist

Published online by Cambridge University Press:  16 March 2012

HAMED HATAMI ,
JAN HLADKÝ ,
DANIEL KRÁL' ,
SERGUEI NORINE  and
ALEXANDER RAZBOROV
HAMED HATAMI
Affiliation:
School of Computer Science, McGill University, Montreal, Canada (e-mail: hatami@cs.mcgill.ca)
JAN HLADKÝ
Affiliation:
Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Malostranské náměstí 25, 118 00 Prague, Czech Republic and DIMAP, Department of Computer Science, University of Warwick, Coventry CV4 7AL, UK (e-mail: honzahladky@gmail.com)
DANIEL KRÁL'
Affiliation:
Institute for Theoretical Computer Science, Faculty of Mathematics and Physics, Charles University, Malostranské náměstí 25, 118 00 Prague, Czech Republic (e-mail: kral@kam.mff.cuni.cz)
SERGUEI NORINE
Affiliation:
Department of Mathematics, Princeton University, Princeton, NJ, USA (e-mail: snorin@math.princeton.edu)
ALEXANDER RAZBOROV
Affiliation:
Department of Computer Science, University of Chicago, IL, USA (e-mail: razborov@cs.uchicago.edu)
Get access Rights & Permissions [Opens in a new window]

Abstract

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 Erdős, Burr and Rosta conjectured that every graph is common. Thomason disproved both conjectures by showing that K4 is not common. It is now known that in fact the common graphs are very rare. Answering a question of Sidorenko and of Jagger, Št'ovíček 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.

Keywords

Primary 05C3505C55
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 21 , Issue 5 , September 2012 , pp. 734 - 742
Copyright
Copyright © Cambridge University Press 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Baber, R. and Talbot, J. (2011) Hypergraphs do jump. Combin. Probab. Comput. 20 161–171.CrossRefGoogle Scholar
[2]Burr, S. A. and Rosta, V. (1980) On the Ramsey multiplicities of graphs: Problems and recent results. J. Graph Theory 4 347–361.CrossRefGoogle Scholar
[3]Chung, F.-R. K., Graham, R. L. and Wilson, R. M. (1989) Quasi-random graphs. Combinatorica 9 345–362.CrossRefGoogle Scholar
[4]Conlon, D., Fox, J. and Sudakov, B. (2010) An approximate version of Sidorenko's conjecture. Geom. Funct. Anal. 20 1354–1366.CrossRefGoogle Scholar
[5]Cummings, J. and Young, M. (2011) Graphs containing triangles are not 3-common. J. Combin. 2 1–14.Google Scholar
[6]Erdős, P. (1962) On the number of complete subgraphs contained in certain graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl. 7 459–464.Google Scholar
[7]Erdős, P. and Simonovits, M. (1984) Cube-supersaturated graphs and related problems. In Progress in Graph Theory: Waterloo, Ont., 1982, Academic Press, pp. 203–218.Google Scholar
[8]Goodman, A. W. (1959) On sets of acquaintances and strangers at any party. Amer. Math. Monthly 66 778–783.CrossRefGoogle Scholar
[9]Grzesik, A. (2011) On the maximum number of C 5's in a triangle-free graph. arXiv:1102.0962.Google Scholar
[10]Hatami, H. (2010) Graph norms and Sidorenko's conjecture. Israel J. Math. 175 125–150.CrossRefGoogle Scholar
[11]Hatami, H., Hladký, J., Král', D., Norine, S. and Razborov, A. (2011) On the number of pentagons in triangle-free graphs. arXiv:1102.1634.Google Scholar
[12]Hladký, J., Král', D. and Norine, S. (2009) Counting flags in triangle-free digraphs. arXiv:0908.2791.CrossRefGoogle Scholar
[13]Jagger, C., Št'ovíček, P. and Thomason, A. (1996) Multiplicities of subgraphs. Combinatorica 16 123–141.CrossRefGoogle Scholar
[14]Razborov, A. A. (2007) Flag algebras. J. Symbolic Logic 72 1239–1282.CrossRefGoogle Scholar
[15]Razborov, A. A. (2010) On 3-hypergraphs with forbidden 4-vertex configurations. SIAM J. Discrete Math. 24 946–963.CrossRefGoogle Scholar
[16]Sidorenko, A. (1989) Cycles in graphs and functional inequalities. Mat. Zametki 46 72–79, 104.Google Scholar
[17]Sidorenko, A. (1991) Inequalities for functionals generated by bipartite graphs. Diskret. Mat. 3 50–65.Google Scholar
[18]Sidorenko, A. (1993) A correlation inequality for bipartite graphs. Graphs Combin. 9 201–204.CrossRefGoogle Scholar
[19]Sidorenko, A. (1996) Randomness friendly graphs. Random Struct. Alg. 8 229–241.3.0.CO;2-#>CrossRefGoogle Scholar
[20]Thomason, A. (1989) A disproof of a conjecture of Erdős in Ramsey theory. J. London Math. Soc. (2) 39 246–255.CrossRefGoogle Scholar