Locally common graphs

DOI10.1002/JGT.22881MaRDI QIDQ6046683zbMATH OpenFDO

Authors Endre Csóka, Tamás Hubai, László Lovász

Publication date 6 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1912.02926, http://hdl.handle.net/10831/89756

zbMATH Keywords

graph homomorphismsgraph limits

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: Goodman proved that the sum of the number of triangles in a graph on $n$ nodes and its complement is at least $n^3/24$; in other words, this sum is minimized, asymptotically, by a random graph with edge density $1/2$. ErdH{o}s conjectured that a similar inequality will hold for $K_4$ in place of $K_3$, but this was disproved by Thomason. But an analogous statement does hold for some other graphs, which are called {it common graphs}. A characterization of common graphs seems, however, out of reach. Franek and R"odl proved that $K_4$ is common in a weaker, local sense. Using the language of graph limits, we study two versions of locally common graphs. We sharpen a result of Jagger, v{S}tov'{i}v{c}ek and Thomason by showing that no graph containing $K_4$ can be locally common, but prove that all such graphs are weakly locally common. We also show that not all connected graphs are weakly locally common.

Recommendations

• Toward characterizing locally common graphs
• Local Density in Graphs with Forbidden Subgraphs
• Graphs containing triangles are not 3-common
• Non-three-colourable common graphs exist
• Multiplicities of subgraphs

Cites work

• scientific article; zbMATH DE number 3885945 (Why is no real title available?)
• scientific article; zbMATH DE number 4216032 (Why is no real title available?)
• 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
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Counting graph homomorphisms
• Generalized quasirandom graphs
• Graph products and monochromatic multiplicities
• Large networks and graph limits
• Limits of dense graph sequences
• Multiplicities of subgraphs
• Non-three-colourable common graphs exist
• On Sets of Acquaintances and Strangers at any Party
• Positive graphs
• Ramsey problem on multiplicities of complete subgraphs in nearly quasirandom graphs
• Sidorenko's conjecture for blow-ups
• Some advances on Sidorenko's conjecture
• Subgraph densities in signed graphons and the local Simonovits-Sidorenko conjecture

Cited in

(6)

• Locally regular graphs
• A Property on Monochromatic Copies of Graphs Containing a Triangle
• On the 3-local profiles of graphs
• Graphs containing triangles are not 3-common
• Toward characterizing locally common graphs
• Non-three-colourable common graphs exist

This page was built for publication: Locally common graphs

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