Name
Abstract | ||
|---|---|---|
AbstractFor a graph G, let piG,i=0,...,3 be the probability that three distinct random vertices span exactly i edges. We call p0G,...,p3G the 3-local profileof 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 p3=0. This planar domain is characterized by an SDP constraint that is derived from Razborov's flag algebra theory. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1002/jgt.21762 | Periodicals |
Keywords | Field | DocType |
local profiles,induced densities,flag algebras | Discrete mathematics,Topology,Graph,Combinatorics,Vertex (geometry),Chordal graph,Planar,Hyperplane,Mathematics,Arbitrarily large | Journal |
Volume | Issue | ISSN |
76 | 3 | 0364-9024 |
Citations | PageRank | References |
4 | 0.69 | 10 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hao Huang | 1 | 589 | 104.49 |
| Nati Linial | 2 | 3872 | 602.77 |
| Humberto Naves | 3 | 24 | 4.08 |
| Yuval Peled | 4 | 8 | 3.22 |
| Benny Sudakov | 5 | 1391 | 159.71 |