Locally common graphs

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

doi:10.1002/jgt.22881

Locally common graphs

J Graph Theory. 2023 Mar;102(3):472-483. doi: 10.1002/jgt.22881. Epub 2022 Sep 2.

Authors

Endre Csóka¹, Tamás Hubai^{1

2}, László Lovász^{1

2}

Affiliations

¹ Combinatorics and Applications Research Division Alfréd Rényi Institute of Mathematics Budapest Hungary.
² Department of Computer Science, Institute of Mathematics Eötvös Loránd University Budapest Hungary.

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. Erdő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 common graphs. Characterization of common graphs seems, however, out of reach. Franek and Rödl 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, Štovíč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.

Keywords: graph homomorphisms; graph theory.