A Property on Monochromatic Copies of Graphs Containing a Triangle

DOI10.1137/23M1564894MaRDI QIDQ6141863zbMATH OpenOpenAlexWikidataFDO

Authors

Publication date 23 January 2024

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

graph limitshomomorphism inequalitiesstrongly common graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Random graphs (graph-theoretic aspects) (05C80) Ramsey theory (05D10)

Abstract: A graph $H$ is called common and respectively, strongly common if the number of monochromatic copies of $H$ in a 2-edge-coloring $phi$ of a large clique is asymptotically minimised by the random coloring with an equal proportion of each color and respectively, by the random coloring with the same proportion of each color as in $phi$. A well-known theorem of Jagger, {v S}t'ov{' i}{v c}ek and Thomason states that every graph containing a $K_4$ is not common. Here we prove an analogous result that every graph containing a $K_3$ and with at least four edges is not strongly common.

Recommendations

• Graphs containing triangles are not 3-common
• Non-bipartite \(k\)-common graphs
• Multiplicities of subgraphs
• Non-three-colourable common graphs exist
• Common graphs with arbitrary connectivity and chromatic number

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
• Common graphs with arbitrary connectivity and chromatic number
• Convex graphon parameters and graph norms
• Cycles in graphs and functional inequalities
• Finite reflection groups and graph norms
• 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?)
• scientific article; zbMATH DE number 3188526 (Why is no real title available?)
• Inequalities for functionals generated by bipartite graphs
• Large networks and graph limits
• Locally common graphs
• Multiplicities of subgraphs
• Non-bipartite \(k\)-common graphs
• Non-three-colourable common graphs exist
• On Sets of Acquaintances and Strangers at any Party
• On the local approach to Sidorenko's conjecture
• On the Ramsey multiplicities of graphs—problems and recent results
• On tripartite common graphs
• Sidorenko's conjecture for blow-ups
• Some advances on Sidorenko's conjecture
• Subgraph densities in signed graphons and the local Simonovits-Sidorenko conjecture
• There exist graphs with super‐exponential Ramsey multiplicity constant
• Toward characterizing locally common graphs

Cited in

(5)

• Non-bipartite \(k\)-common graphs
• Extended commonality of paths and cycles via Schur convexity
• Off-diagonal commonality of graphs via entropy
• On the uncommonness of minimal rank-2 systems of linear equations
• Disconnected common graphs via supersaturation

This page was built for publication: A Property on Monochromatic Copies of Graphs Containing a Triangle

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