On the 3-local profiles of graphs

DOI10.1002/JGT.21762MaRDI QIDQ5495884zbMATH OpenOpenAlexFDO

Authors Hao Huang, Nathan Linial, Humberto Naves, Yuval Peled, Benny Sudakov

Publication date 7 August 2014

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1211.3106

zbMATH Keywords

flag algebrasinduced densitieslocal profiles

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Structural characterization of families of graphs (05C75) Random graphs (graph-theoretic aspects) (05C80)

Abstract: 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 ${calS}_{3}subsetmathbb{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 ${calS}_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_3geq 1/4. We also give a full description of the triangle-free case, i.e., the intersection of ${calS}_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.

Recommendations

• On the local profiles of trees
• On the local structure of oriented graphs -- a case study in flag algebras
• Locally common graphs
• Tropicalization of graph profiles
• The chromatic profile of locally colourable graphs

Cites work

• 2-colorings of complete graphs with a small number of monochromatic \(K_ 4\) subgraphs
• A Disproof of a Conjecture of Erdős in Ramsey Theory
• Flag algebras
• scientific article; zbMATH DE number 4061279 (Why is no real title available?)
• scientific article; zbMATH DE number 3189757 (Why is no real title available?)
• On 3-hypergraphs with forbidden 4-vertex configurations
• On Sets of Acquaintances and Strangers at any Party
• On the Minimal Density of Triangles in Graphs
• On the structure of linear graphs
• Sur le problème de Goodman pour les quadrangles et la majoration des nombres de Ramsey
• The inducibility of blow-up graphs
• The inducibility of complete bipartite graphs
• The inducibility of graphs
• The maximal number of induced complete bipartite graphs
• The number of cliques in graphs of given order and size
• Undecidability of linear inequalities in graph homomorphism densities

Cited in

(17)

• The feasible region of induced graphs
• On the local structure of oriented graphs -- a case study in flag algebras
• On the number of 4-cycles in a tournament
• On the local profiles of trees
• Extremal edge polytopes
• A note on the inducibility of 4-vertex graphs
• Graphs with Few 3‐Cliques and 3‐Anticliques are 3‐Universal
• Inducibility and universality for trees
• Tropicalization of graph profiles
• Paths vs. stars in the local profile of trees
• The exact minimum number of triangles in graphs with given order and size
• The feasible region for consecutive patterns of permutations is a cycle polytope
• New Ramsey multiplicity bounds and search heuristics
• The complexity of homomorphism reconstructibility
• Two local and one global properties of 3-connected graphs on compact 2-dimensional manifolds
• The complexity of homomorphism reconstructibility
• Getting to the root of the problem: sums of squares for limits of trees

This page was built for publication: On the 3-local profiles of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495884)