×

zbMATH — the first resource for mathematics

On the minimal density of triangles in graphs. (English) Zbl 1170.05036
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
PDF BibTeX XML Cite
Full Text: DOI
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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.