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
Cites work
- A correlation inequality for bipartite graphs
- A Disproof of a Conjecture of Erdős in Ramsey Theory
- An approximate version of Sidorenko's conjecture
- Flag algebras
- Graph norms and Sidorenko's conjecture
- Graphs containing triangles are not 3-common
- scientific article; zbMATH DE number 903461 (Why is no real title available?)
- 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
(41)- Finitely forcible graph limits are universal
- The step Sidorenko property and non-norming edge-transitive graphs
- Extremal problems and results related to Gallai-colorings
- Threshold Ramsey multiplicity for paths and even cycles
- Non-bipartite \(k\)-common graphs
- Minimum number of edges that occur in odd cycles
- Compactness and finite forcibility of graphons
- On the algebraic and topological structure of the set of Turán densities
- Graph theory. Abstracts from the workshop held January 2--8, 2022
- On crossing numbers of complete tripartite and balanced complete multipartite graphs
- More about sparse halves in triangle-free graphs
- A new lower bound based on Gromov's method of selecting heavily covered points
- Weak regularity and finitely forcible graph limits
- Monochromatic triangles in three-coloured graphs
- Finitely forcible graphons and permutons
- A new bound for the 2/3 conjecture
- Threshold Ramsey multiplicity for odd cycles
- Finitely forcible graphons with an almost arbitrary structure
- Decomposing graphs into edges and triangles
- On the density of transitive tournaments
- Minimum Number of Monotone Subsequences of Length 4 in Permutations
- On tripartite common graphs
- Locally common graphs
- Combinatorics. Abstracts from the workshop held January 1--7, 2023
- Toward characterizing locally common graphs
- A Property on Monochromatic Copies of Graphs Containing a Triangle
- Common graphs with arbitrary connectivity and chromatic number
- Extended commonality of paths and cycles via Schur convexity
- Graphs containing triangles are not 3-common
- Off-diagonal commonality of graphs via entropy
- On uncommon systems of equations
- A new family of Sidorenko linear configurations
- Common pairs of graphs
- Counting odd cycles in sparse pseudorandom graphs
- On the uncommonness of minimal rank-2 systems of linear equations
- Common graphs with arbitrary chromatic number
- The dimension of the region of feasible tournament profiles
- Turán colourings in off-diagonal Ramsey multiplicity
- The dimension of the feasible region of pattern densities
- Disconnected common graphs via supersaturation
- Ramsey multiplicity of apices of trees
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)
