On the 3-local profiles of graphs

Hao Huang, Nati Linial, Humberto Naves, Yuval Peled, Benny Sudakov

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


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),.,p 3(G)) the 3-local profile of G. We investigate the set S3'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 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≥14. We also give a full description of the triangle-free case, i.e. the intersection of S3 with the hyperplane p 3=0. This planar domain is characterized by an SDP constraint that is derived from Razborov's flag algebra theory.

שפה מקוריתאנגלית אמריקאית
עמודים (מ-עד)236-248
מספר עמודים13
כתב עתJournal of Graph Theory
מספר גיליון3
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - יולי 2014

ASJC Scopus subject areas

  • ???subjectarea.asjc.2600.2608???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'On the 3-local profiles of graphs'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי