Premium
On the 3‐Local Profiles of Graphs
Author(s) -
Huang Hao,
Linial Nati,
Naves Humberto,
Peled Yuval,
Sudakov Benny
Publication year - 2014
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21762
Subject(s) - mathematics , combinatorics , hyperplane , vertex (graph theory) , intersection (aeronautics) , planar graph , discrete mathematics , graph , engineering , aerospace engineering
Abstract For a graph G , letp 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 setS 3 ⊂ R 4of 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 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 inequalityp 0 + p 3 ≥ 1 4 . We also give a full description of the triangle‐free case, i.e. the intersection of S 3 with the hyperplanep 3 = 0 . This planar domain is characterized by an SDP constraint that is derived from Razborov's flag algebra theory.