On the Minimal Density of Triangles in Graphs
On the Minimal Density of Triangles in Graphs
复制标题
关于图中三角形的最小密度
DOI：
10.1017/s0963548308009085
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
A. Razborov
中科院分区：
文献类型：
--
作者：
A. Razborov
对于固定的ρ∈[0，1]，边密度为ρ的图中三角形的最小可能密度g3(ρ)(渐近地)是多少？我们通过证明$$g_3(\rho)=\frac{(t-1)\ofb{t-2\sqrt{t(t-\rho(t+1))}}\ofb{t+\sqrt{t(t-\rho(t+1))}}^2}{t^2(t+1)^2}，$$其中$t\df\lFloor 1/(1-\rho)\rFloor$是使得$\rho\in\Bigl[1-\FRAC 1t，1-\FRAC 1{t+1}\BiGR]$的整数，从而完全解决了这个问题。
For a fixed ρ ∈ [0, 1], what is (asymptotically) the minimal possible density g3(ρ) of triangles in a graph with edge density ρ? We completely solve this problem by proving that $$ g_3(\rho) =\frac{(t-1)\ofb{t-2\sqrt{t(t-\rho(t+1))}}\ofb{t+\sqrt{t(t-\rho(t+1))}}^2}{t^2(t+1)^2},$$ 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]$.