2012/11/13 by Hao Huang, Nati Linial, Huang, Hao +7
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1211.3106
openalex publication_date 2012/11/13 · arxiv created 2013/12/08 · arxiv updated 2013/12/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a graph G, let pi(G), i=0,...,3 be the probability that three distinct random vertices span exactly i edges. We call (p0(G),...,p3(G)) the 3-local profile of G. We investigate the set \cal S3 ⊂ \mathbb R4 of all vectors (p0,...,p3) that are arbitrarily close to the 3-local profiles of arbitrarily large graphs. We give a full description of the projection of \cal S3 to the (p0, p3) 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 p0+p3≥ 1/4. We also give a full description of the triangle-free case, i.e., the intersection of \cal S3 with the hyperplane p3=0. This planar domain is characterized by an SDP constraint that is derived from Razborov's flag algebra theory.