Non-three-colourable common graphs exist

DOI10.1017/S0963548312000107MaRDI QIDQ2911071zbMATH OpenDBLPWikidataFDO

Authors Hamed Hatami, Jan Hladký, Daniel Král', Serguei Norine, Alexander Razborov

Publication date 12 September 2012

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1105.0307

zbMATH Keywords

5-wheelcommon graphsnumber of copies

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55)

Abstract: A graph H is called common if the total number of copies of H in every graph and its complement asymptotically minimizes for random graphs. A former conjecture of Burr and Rosta, extending a conjecture of Erdos asserted that every graph is common. Thomason disproved both conjectures by showing that the complete graph of order four is not common. It is now known that in fact the common graphs are very rare. Answering a question of Sidorenko and of Jagger, Stovicek 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-colorable.

Recommendations

• Multiplicities of subgraphs
• Locally common graphs
• Graphs containing triangles are not 3-common
• On tripartite common graphs
• Common graphs with arbitrary connectivity and chromatic number

Cites work

• scientific article; zbMATH DE number 903461 (Why is no real title available?)
• A Disproof of a Conjecture of Erdős in Ramsey Theory
• A correlation inequality for bipartite graphs
• An approximate version of Sidorenko's conjecture
• Flag algebras
• Graph norms and Sidorenko's conjecture
• Graphs containing triangles are not 3-common
• Hypergraphs do jump
• Multiplicities of subgraphs
• On 3-hypergraphs with forbidden 4-vertex configurations
• On Sets of Acquaintances and Strangers at any Party
• On the Ramsey multiplicities of graphs—problems and recent results
• Quasi-random graphs

Cited in

(31)

• The step Sidorenko property and non-norming edge-transitive graphs
• A new bound for the 2/3 conjecture
• Finitely forcible graph limits are universal
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• Graphs containing triangles are not 3-common
• A new lower bound based on Gromov's method of selecting heavily covered points
• Minimum number of edges that occur in odd cycles
• Minimum Number of Monotone Subsequences of Length 4 in Permutations
• A Property on Monochromatic Copies of Graphs Containing a Triangle
• On crossing numbers of complete tripartite and balanced complete multipartite graphs
• On the algebraic and topological structure of the set of Turán densities
• Threshold Ramsey multiplicity for paths and even cycles
• Non-bipartite \(k\)-common graphs
• More about sparse halves in triangle-free graphs
• On uncommon systems of equations
• On the density of transitive tournaments
• Extremal problems and results related to Gallai-colorings
• Decomposing graphs into edges and triangles
• Extended commonality of paths and cycles via Schur convexity
• Off-diagonal commonality of graphs via entropy
• Finitely forcible graphons with an almost arbitrary structure
• Threshold Ramsey multiplicity for odd cycles
• Toward characterizing locally common graphs
• Compactness and finite forcibility of graphons
• Graph theory. Abstracts from the workshop held January 2--8, 2022
• Locally common graphs
• Weak regularity and finitely forcible graph limits
• Finitely forcible graphons and permutons
• Common graphs with arbitrary connectivity and chromatic number
• Monochromatic triangles in three-coloured graphs
• On tripartite common graphs

This page was built for publication: Non-three-colourable common graphs exist

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2911071)