Locally common graphs.

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.