On the Minimal Density of Triangles in Graphs 论文

摘要

For a fixed ρ ∈ [0, 1], what is (asymptotically) the minimal possible density g 3 (ρ) of triangles in a graph with edge density ρ? We completely solve this problem by proving that where $t\df \lfloor 1/(1-\rho)\rfloor$ is the integer such that $\rho\in\bigl[ 1-\frac 1t,1-\frac 1{t+1}\bigr]$ .