On the 3-local profiles of graphs

For a graph G, let p_i(G), i=0,…,3 be the probability that three distinct random vertices span exactly i edges. We call (p_0(G),…,p_3(G)) the 3-local profile of G. We investigate the set ${\mathcal{S}}_3\subset {\mathbb{R}}^4$ of all vectors (p_0,…,p_3) that are arbitrarily close to the 3-local profiles of arbitrarily large graphs. We give a full description of the projection of ${\mathcal{S}}_3$ to the (p_0, p_3) plane. The upper envelope of this planar domain is obtained from cliques on a fraction of the vertex set and complements of such graphs. The lower envelope is Goodman’s inequality p_0+p_3\geq 1/4. We also give a full description of the triangle-free case, i.e., the intersection of ${\mathcal{S}}_3$ with the hyperplane p_3=0. This planar domain is characterized by an SDP constraint that is derived from Razborov’s flag algebra theory.