## Abstract

For a graph G, let pi(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 S3'R4 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 S3 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_{3}≥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.

Original language | English (US) |
---|---|

Pages (from-to) | 236-248 |

Number of pages | 13 |

Journal | Journal of Graph Theory |

Volume | 76 |

Issue number | 3 |

DOIs | |

State | Published - Jul 2014 |

## Keywords

- flag algebras
- induced densities
- local profiles