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)

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