On the minimal density of triangles in graphs. (English) Zbl 1170.05036

Razborov, Alexander A.

Comb. Probab. Comput. 17, No. 4, 603-618 (2008).

Summary: For a fixed \(\rho\in[0,1]\), what is (asymptotically) the minimal possible density \(g_3(\rho)\) of triangles in a graph with edge density \(\rho\)? We completely solve this problem by proving that
\[ g_3(\rho)= \frac{(t-1)\big(t-2\sqrt{t(t-\rho(t+1))}\big) \big(t+\sqrt{t(t-\rho(t+1))}\big)^2}{t^2(t+1)^2}, \] where \(t \overset\text{def}= \lfloor 1/(1-\rho)\rfloor\) is the integer such that \(\rho\in[1-\frac 1t,1-\frac 1{t+1}]\).

MSC:

05C35	Extremal problems in graph theory
05E10	Combinatorial aspects of representation theory

Keywords:

graph; density of triangles

References:

[1]	DOI: 10.1002/jgt.3190130411 · Zbl 0673.05046 · doi:10.1002/jgt.3190130411
[2]	DOI: 10.1007/BF02579292 · Zbl 0529.05027 · doi:10.1007/BF02579292
[3]	DOI: 10.2178/jsl/1203350785 · Zbl 1146.03013 · doi:10.2178/jsl/1203350785
[4]	Tur?n, Mat. ?s Fiz. Lapok 48 pp 436– (1941)
[5]	Erd?s, Casopis Pest. Mat. 94 pp 290– (1969)
[6]	DOI: 10.1016/S0020-0190(00)00086-7 · Zbl 1339.05231 · doi:10.1016/S0020-0190(00)00086-7
[7]	Erd?s, Illinois J. Math. 6 pp 122– (1962)
[8]	Moon, Magyar. Tud. Akad. Mat. Kutat? Int. K?zl 7 pp 283– (1962)
[9]	Mantel, Wiskundige Opgaven 10 pp 60– (1907)
[10]	Khad?iivanov, Serdica 4 pp 344– (1978)
[11]	DOI: 10.2307/2310464 · Zbl 0092.01305 · doi:10.2307/2310464
[12]	Nordhaus, Canadian J. Math. 15 pp 33– (1963) · Zbl 0115.17403 · doi:10.4153/CJM-1963-004-7