Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-23T14:13:30.516Z Has data issue: false hasContentIssue false
  • English
  • Français

Asymptotic Structure of Graphs with the Minimum Number of Triangles

Part of: Graph theory

Published online by Cambridge University Press:  04 May 2016

OLEG PIKHURKO  and
ALEXANDER RAZBOROV
OLEG PIKHURKO
Affiliation:
Mathematics Institute and DIMAP, University of Warwick, Coventry CV4 7AL, UK (e-mail: [email protected])
ALEXANDER RAZBOROV
Affiliation:
Department of Computer Science, University of Chicago, Chicago, IL 60637, USA (e-mail: [email protected])
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.

We consider the problem of minimizing the number of triangles in a graph of given order and size, and describe the asymptotic structure of extremal graphs. This is achieved by characterizing the set of flag algebra homomorphisms that minimize the triangle density.

MSC classification

Primary: 05C35: Extremal problems
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 1 , January 2017 , pp. 138 - 160
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright
Copyright © Cambridge University Press 2016

References

[1] Aristoff, D. and Radin, C. (2013) Emergent structures in large networks. J. Appl. Probab. 50 883–888.Google Scholar
[2] Bollobás, B. (1976) On complete subgraphs of different orders. Math. Proc. Camb. Phil. Soc. 79 19–24.Google Scholar
[3] Borgs, C., Chayes, J., Lovász, L., Sós, V. T. and Vesztergombi, K. (2008) Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing. Adv. Math. 219 1801–1851.Google Scholar
[4] Chatterjee, S. and Dembo, A. (2014) Nonlinear large deviations. arXiv:1401.3495 Google Scholar
[5] Chatterjee, S. and Dey, P. S. (2010) Applications of Stein's method for concentration inequalities. Ann. Probab. 38 2443–2485.Google Scholar
[6] Chatterjee, S. and Diaconis, P. (2013) Estimating and understanding exponential random graph models. Ann. Statist. 41 2428–2461.CrossRefGoogle Scholar
[7] Chatterjee, S. and Varadhan, S. R. S. (2011) The large deviation principle for the Erdős–Rényi random graph. Europ. J. Combin. 32 1000–1017.Google Scholar
[8] Cummings, J., Král', D., Pfender, F., Sperfeld, K., Treglown, A. and Young, M. (2013) Monochromatic triangles in three-coloured graphs. J. Combin. Theory Ser. B 103 489–503.Google Scholar
[9] Das, S., Huang, H., Ma, J., Naves, H. and Sudakov, B. (2013) A problem of Erdős on the minimum number of k-cliques. J. Combin. Theory Ser. B 103 344–373.Google Scholar
[10] Erdős, P. (1955) Some theorems on graphs. Riveon Lematematika 9 13–17.Google Scholar
[11] Erdős, P. (1962) On a theorem of Rademacher–Turán. Illinois J. Math. 6 122–127.Google Scholar
[12] Erdős, P. (1967) Some recent results on extremal problems in graph theory: Results. In Theory of Graphs: Rome 1966, Gordon and Breach, pp. 117–123 (English); pp. 124–130 (French).Google Scholar
[13] Erdős, P. (1969) On the number of complete subgraphs and circuits contained in graphs. Časopis Pěst. Mat. 94 290–296.Google Scholar
[14] Erdős, P., Frankl, P. and Rödl, V. (1986) The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent. Graphs Combin. 2 113–121.Google Scholar
[15] Fisher, D. C. (1989) Lower bounds on the number of triangles in a graph. J. Graph Theory 13 505–512.Google Scholar
[16] Frieze, A. and Kannan, R. (1999) Quick approximation to matrices and applications. Combinatorica 19 175–220.CrossRefGoogle Scholar
[17] Hatami, H., Hladký, J., Král', D., Norine, S. and Razborov, A. (2013) On the number of pentagons in triangle-free graphs. J. Combin. Theory Ser. A 120 722–732.Google Scholar
[18] Komlós, J. and Simonovits, M. (1996) Szemerédi's regularity lemma and its applications to graph theory. In Combinatorics: Paul Erdős is Eighty (Miklós, D., Sós, V. T. and Szőnyi, T., eds), Vol. 2, Bolyai Mathematical Society, pp. 295–352.Google Scholar
[19] Lovász, L. (2012) Large Networks and Graph Limits, Colloquium Publications, AMS.Google Scholar
[20] Lovász, L. and Simonovits, M. (1976) On the number of complete subgraphs of a graph. In Proc. 5th British Combinatorial Conference: Aberdeen 1975. Congress. Numer. XV 431–441.Google Scholar
[21] 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
[22] Lovász, L. and Szegedy, B. (2006) Limits of dense graph sequences. J. Combin. Theory Ser. B 96 933–957.Google Scholar
[23] Lubetzky, E. and Zhao, Y. (2014) On the variational problem for upper tails in sparse random graphs. arXiv:1402.6011 Google Scholar
[24] Lubetzky, E. and Zhao, Y. (2015) On replica symmetry of large deviations in random graphs. Random Struct. Alg. 47 109–146.Google Scholar
[25] Mantel, W. (1907) Problem 28. Winkundige Opgaven 10 60–61.Google Scholar
[26] Moon, J. W. and Moser, L. (1962) On a problem of Turán. Publ. Math. Inst. Hungar. Acad. Sci. 7 283–287.Google Scholar
[27] Nikiforov, V. (2011) The number of cliques in graphs of given order and size. Trans. Amer. Math. Soc. 363 1599–1618.Google Scholar
[28] Nordhaus, E. A. and Stewart, B. M. (1963) Triangles in an ordinary graph. Canad. J. Math. 15 33–41.Google Scholar
[29] Pikhurko, O. (2011) The minimum size of 3-graphs without four vertices spanning no or exactly three edges. Europ. J. Combin. 23 1142–1155.Google Scholar
[30] Pikhurko, O. and Vaughan, E. R. (2013) Minimum number of k-cliques in graphs with bounded independence number. Combin. Probab. Comput. 22 910–934.Google Scholar
[31] Radin, C. and Sadun, L. (2013) Phase transitions in a complex network. J. Phys. A 46 305002.CrossRefGoogle Scholar
[32] Radin, C. and Yin, M. (2013) Phase transitions in exponential random graphs. Ann. Appl. Prob. 23 2458–2471.Google Scholar
[33] Radin, C., Ren, K. and Sadun, L. (2014) The asymptotics of large constrained graphs. J. Phys. A 47 175001.Google Scholar
[34] Razborov, A. (2007) Flag algebras. J. Symbol. Logic 72 1239–1282.Google Scholar
[35] Razborov, A. (2008) On the minimal density of triangles in graphs. Combin. Probab. Comput. 17 603–618.Google Scholar
[36] Reiher, C. (2012) The clique density theorem. arXiv:1212.2454 Google Scholar
[37] Ruzsa, I. Z. and Szemerédi, E. (1978) Triple systems with no six points carrying three triangles. In Combinatorics II (Hajnal, A. and Sós, V., eds), North-Holland, pp. 939–945.Google Scholar
[38] Simonovits, M. (1968) A method for solving extremal problems in graph theory, stability problems. In Theory of Graphs: Tihany 1966, Academic, pp. 279–319.Google Scholar
[39] Turán, P. (1941) On an extremal problem in graph theory (in Hungarian). Mat. Fiz. Lapok 48 436–452.Google Scholar