Goodman proved that the sum of the number of triangles in a graph on nodes and its
complement is at least ; 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 in place of , 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 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 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.
