Densities of 3-vertex graphs

2016/10/07 by Roman Glebov, Andrzej Grzesik, Glebov, Roman +9
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1610.02446

openalex publication_date 2016/10/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let d_i(G) be the density of the 3-vertex i-edge graph in a graph G, i.e., the probability that three random vertices induce a subgraph with i edges. Let S be the set of all quadruples (d₀,d₁,d₂,d₃) that are arbitrary close to 3-vertex graph densities in arbitrary large graphs. Huang, Linial, Naves, Peled and Sudakov have recently determined the projection of the set S to the (d₀,d₃) plane. We determine the projection of the set S to all the remaining planes.

Citations

• On the minimal monochromatic K4-density

Related

• On the Density of a Graph and its Blowup
• 3-Symmetric Graphs
• On the 3-local profiles of graphs
• On the density of triangles and squares in regular finite and unimodular random graphs
• On the minimum bisection of random 3-regular graphs