Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-10T13:38:11.447Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Minimal Density of Triangles in Graphs

Published online by Cambridge University Press:  01 July 2008

ALEXANDER A. RAZBOROV
ALEXANDER A. RAZBOROV*
Affiliation:
Institute for Advanced Study, Princeton, USA and Steklov Mathematical Institute, Moscow, Russia (e-mail: razborov@ias.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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]$.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 17 , Issue 4 , July 2008 , pp. 603 - 618
Copyright
Copyright © Cambridge University Press 2008

References

[1]Bollobás, B. (1975) Relations between sets of complete subgraphs. In Proc. Fifth British Combin. Conference, pp. 79–84.Google Scholar
[2]Bollobás, B. (1978) Extremal Graph Theory, Academic Press.CrossRefGoogle Scholar
[3]Borgs, C., Chayes, J., Lovász, L., Sós, V. T. and Vesztergombi, K. (2006) Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing. Manuscript, available at http://arxiv.org/abs/math/0702004.Google Scholar
[4]Erdős, P. (1962) On a theorem of Rademacher–Turán. Illinois J. Math. 6 122–127.CrossRefGoogle Scholar
[5]Erdős, P. (1969) On the number of complete subgraphs contained in certain graphs. Casopis Pest. Mat. 94 290–296.CrossRefGoogle Scholar
[6]Erdős, P. and Spencer, J. (1974) Probabilistic Methods in Combinatorics, Academic Press.Google Scholar
[7]Erdős, P. and Simonovits, M. (1983) Supersaturated graphs and hypergraphs. Combinatorica 3 181–192.CrossRefGoogle Scholar
[8]Felix, D. (2005) Asymptotic relations in flag algebras. Manuscript, available at http://math.ucsd.edu/~dfelix/partialorder.pdf.Google Scholar
[9]Fisher, D. (1989) Lower bounds on the number of triangles in a graph. J. Graph Theory 13 505–512.CrossRefGoogle Scholar
[10]Goldwurm, M. and Santini, M. (2000) Clique polynomials have a unique root of smallest modulus. Inform. Process. Lett. 75 127–132.CrossRefGoogle Scholar
[11]Goodman, A. W. (1959) On sets of acquaintances and strangers at any party. Amer. Math. Monthly 66 778–783.CrossRefGoogle Scholar
[12]Khadžiivanov, N. and Nikiforov, V. (1978) The Nordhaus–Stewart–Moon–Moser inequality. Serdica 4 344–350. In Russian.Google Scholar
[13]Lovász, L. and Simonovits, M. (1983) On the number of complete subgraphs of a graph II. In Studies in Pure Mathematics, Birkhäuser, pp. 459–495.CrossRefGoogle Scholar
[14]Mantel, W. (1907) Problem 28: Solution by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh and W. A. Wythoff. Wiskundige Opgaven 10 60–61.Google Scholar
[15]Moon, J. W. and Moser, L. (1962) On a problem of Turán. Magyar. Tud. Akad. Mat. Kutató Int. Közl 7 283–286.Google Scholar
[16]Nikiforov, V. (2007) The number of cliques in graphs of given order and size. Manuscript, available at http://arxiv.org/abs/0710.2305v2 (version 2).Google Scholar
[17]Nordhaus, E. A. and Stewart, B. M. (1963) Triangles in an ordinary graph. Canadian J. Math. 15 33–41.CrossRefGoogle Scholar
[18]Podolskii, V. V. (2006) Master's thesis, Moscow State University, Moscow. In Russian.Google Scholar
[19]Razborov, A. (2007) Flag algebras. J. Symbolic Logic 72 1239–1282.CrossRefGoogle Scholar
[20]Turán, P. (1941) Egy gráfelméleti szélsöértékfeladatról. Mat. és Fiz. Lapok 48 436–453.Google Scholar