On the 3‐Local Profiles of Graphs. Issue 3 (23rd August 2013) - Huang, Hao; Linial, Nati; Naves, Humberto; Peled, Yuval; Sudakov, Benny
Abstract For a graph G, let <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg5f98z0g6" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />pi(G), i=0, ..., 3</alternatives> be the probability that three distinct random vertices span exactly i edges. We call <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg5f98z0cj" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />(p0(G), ..., p3(G))</alternatives> the 3‐local profile of G. We investigate the set <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg5f98z09f" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />S3⊂R4</alternatives> of all vectors <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg5f98z1gq" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />(p0, ..., p3)</alternatives> that are arbitrarily close to the 3‐local profiles of arbitrarily large graphs. We give a full description of the projection of <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg5f98z1jt" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />S3</alternatives> to the <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg5f98z19z" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />(p0, p3)</alternatives> 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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg5f98z1c2" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />p0+p3≥14</alternatives>. We also give a full description of the triangle‐free case, i.e. the intersection of <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg5f98z1p1" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />S3</alternatives> with the hyperplane <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg5f98z1qk" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />p3=0</alternatives>. This planar domain is characterized by an SDP constraint that is derived from Razborov's flag algebra theory.