Locally common graphs

DOI10.1002/JGT.22881zbMATH Open1522.05312arXiv1912.02926MaRDI QIDQ6046683FDOQ6046683

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)

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.

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

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

zbMATH Keywords

graph homomorphismsgraph limits

Mathematics Subject Classification ID

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

Cites Work

• Limits of dense graph sequences
• Large networks and graph limits
• Non-three-colourable common graphs exist
• Counting graph homomorphisms
• Generalized quasirandom graphs
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• On Sets of Acquaintances and Strangers at any Party
• Title not available (Why is that?)
• A correlation inequality for bipartite graphs
• Title not available (Why is that?)
• Multiplicities of subgraphs
• A Disproof of a Conjecture of Erdős in Ramsey Theory
• Graph products and monochromatic multiplicities
• Subgraph densities in signed graphons and the local Simonovits-Sidorenko conjecture
• Some advances on Sidorenko's conjecture
• Ramsey problem on multiplicities of complete subgraphs in nearly quasirandom graphs
• Sidorenko's conjecture for blow-ups
• Title not available (Why is that?)
• Positive graphs

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)