The clique density theorem

Abstract

Turán’s theorem is a cornerstone of extremal graph theory. It asserts that for any integer $r \geqslant 2$, every graph on $n$ vertices with more than ${\tfrac{r-2}{2(r-1)}\cdot n^2}$ edges contains a clique of size $r$, i.e., $r$ mutually adjacent vertices. The corresponding extremal graphs are balanced $(r-1)$-partite graphs.
The question as to how many such $r$-cliques appear at least in any $n$-vertex graph with $\gamma n^2$ edges has been intensively studied in the literature. In particular, Lov\’asz and Simonovits conjectured in the 1970’s that asymptotically the best possible lower bound is given by the complete multipartite graph with $\gamma n^2$ edges in which all but one vertex class is of the same size while the remaining one may be smaller.
Their conjecture was recently resolved for $r=3$ by Razborov and for $r=4$ by Nikiforov. In this article, we prove the conjecture for all values of $r$.

  • [BolRaz] B. Bollobás, "Relations between sets of complete subgraphs," in Proceedings of the Fifth British Combinatorial Conference, Winnipeg, Man., 1976, pp. 79-84.
    @INPROCEEDINGS{BolRaz, mrkey = {0396327},
      author = {Bollob{á}s, B{é}la},
      mrclass = {05C35},
      SERIES={Congressus Numerantium},
      VOLUME={XV},
      address = {Winnipeg, Man.},
      publisher = {Utilitas Math.},
      zblnumber = {0325.05118},
      mrnumber = {0396327},
      booktitle = {Proceedings of the {F}ifth {B}ritish {C}ombinatorial {C}onference},
      venue = {{U}niv. {A}berdeen, {A}berdeen, 1975},
      mrreviewer = {E. A. Nordhaus},
      title = {Relations between sets of complete subgraphs},
      pages = {79--84},
      year = {1976},
      }
  • [Csik] Go to document P. Csikvári, "Note on the smallest root of the independence polynomial," Combin. Probab. Comput., vol. 22, iss. 1, pp. 1-8, 2013.
    @ARTICLE{Csik, mrkey = {3002570},
      number = {1},
      issn = {0963-5483},
      author = {Csikv{á}ri, P{é}ter},
      mrclass = {05C31},
      doi = {10.1017/S0963548312000302},
      journal = {Combin. Probab. Comput.},
      zblnumber = {1257.05066},
      volume = {22},
      mrnumber = {3002570},
      fjournal = {Combinatorics, Probability and Computing},
      mrreviewer = {Mohammad Reza Oboudi},
      title = {Note on the smallest root of the independence polynomial},
      year = {2013},
      pages = {1--8},
      }
  • [Fish] Go to document D. C. Fisher, "Lower bounds on the number of triangles in a graph," J. Graph Theory, vol. 13, iss. 4, pp. 505-512, 1989.
    @ARTICLE{Fish, mrkey = {1010583},
      number = {4},
      issn = {0364-9024},
      author = {Fisher, David C.},
      mrclass = {05C35},
      doi = {10.1002/jgt.3190130411},
      journal = {J. Graph Theory},
      zblnumber = {0673.05046},
      volume = {13},
      mrnumber = {1010583},
      fjournal = {Journal of Graph Theory},
      mrreviewer = {Endre Boros},
      coden = {JGTHDO},
      title = {Lower bounds on the number of triangles in a graph},
      year = {1989},
      pages = {505--512},
      }
  • [GolSan] Go to document M. Goldwurm and M. Santini, "Clique polynomials have a unique root of smallest modulus," Inform. Process. Lett., vol. 75, iss. 3, pp. 127-132, 2000.
    @ARTICLE{GolSan, mrkey = {1776664},
      number = {3},
      issn = {0020-0190},
      author = {Goldwurm, Massimiliano and Santini, Massimo},
      mrclass = {05C50 (68Q45)},
      doi = {10.1016/S0020-0190(00)00086-7},
      journal = {Inform. Process. Lett.},
      volume = {75},
      mrnumber = {1776664},
      fjournal = {Information Processing Letters},
      coden = {IFPLAT},
      title = {Clique polynomials have a unique root of smallest modulus},
      year = {2000},
      pages = {127--132},
      zblnumber = {06594123},
     }
  • [Goodman] Go to document A. W. Goodman, "On sets of acquaintances and strangers at any party," Amer. Math. Monthly, vol. 66, pp. 778-783, 1959.
    @ARTICLE{Goodman, mrkey = {0107610},
      issn = {0002-9890},
      author = {Goodman, A. W.},
      mrclass = {05.00},
      doi = {10.2307/2310464},
      journal = {Amer. Math. Monthly},
      zblnumber = {0092.01305},
      volume = {66},
      mrnumber = {0107610},
      fjournal = {The American Mathematical Monthly},
      mrreviewer = {A. M. Gleason},
      title = {On sets of acquaintances and strangers at any party},
      year = {1959},
      pages = {778--783},
      }
  • [Had-Nik] N. G. Hadvziivanov and V. S. Nikiforov, "The Nordhaus-Stewart-Moon-Moser inequality," Serdica, vol. 4, iss. 4, pp. 344-350, 1978.
    @ARTICLE{Had-Nik, mrkey = {0543156},
      number = {4},
      issn = {0204-4110},
      author = {Had{ž}iivanov, Nikola{\u\i} G. and Nikiforov, Vladimir S.},
      mrclass = {05C35},
      journal = {Serdica},
      zblnumber = {0475.05051},
      volume = {4},
      mrnumber = {0543156},
      fjournal = {Serdica. Bulgaricae Mathematicae Publicationes},
      mrreviewer = {B. Zelinka},
      coden = {SERDDJ},
      title = {The {N}ordhaus-{S}tewart-{M}oon-{M}oser inequality},
      year = {1978},
      pages = {344--350},
      }
  • [LovSim] L. Lovász and M. Simonovits, "On the number of complete subgraphs of a graph. II," in Stud in Pure Mathematics, Mem. of P. Turan, Basel: Birkhäuser, 1983, pp. 459-495.
    @incollection{LovSim, MRKEY={0820244},
      AUTHOR={Lov\'{a}sz, L\'{a}szló and Simonovits, Miklós},
      TITLE={On the number of complete subgraphs of a graph. {II}},
      BOOKTITLE={Stud in Pure Mathematics, Mem. of P. Turan},
      PAGES={459--495},
      PUBLISHER={Birkhäuser},
      ADDRESS = {Basel},
      YEAR={1983},
      MRNUMBER={0820244},
      ZBLNUMBER={0519.05042},
      }
  • [Momo] J. W. Moon and L. Moser, "On a problem of Turán," Magyar Tud. Akad. Mat. Kutató Int. Közl., vol. 7, pp. 283-286, 1962.
    @ARTICLE{Momo, mrkey = {0151955},
      author = {Moon, J. W. and Moser, L.},
      mrclass = {55.10 (05.65)},
      journal = {Magyar Tud. Akad. Mat. Kutató Int. Közl.},
      zblnumber = {0114.01206},
      volume = {7},
      mrnumber = {0151955},
      mrreviewer = {R. C. Read},
      title = {On a problem of {T}urán},
      year = {1962},
      pages = {283--286},
      }
  • [Nik] Go to document V. Nikiforov, "The number of cliques in graphs of given order and size," Trans. Amer. Math. Soc., vol. 363, iss. 3, pp. 1599-1618, 2011.
    @ARTICLE{Nik, mrkey = {2737279},
      number = {3},
      issn = {0002-9947},
      author = {Nikiforov, V.},
      mrclass = {05C30 (05C69)},
      doi = {10.1090/S0002-9947-2010-05189-X},
      journal = {Trans. Amer. Math. Soc.},
      zblnumber = {1231.05129},
      volume = {363},
      mrnumber = {2737279},
      fjournal = {Transactions of the American Mathematical Society},
      coden = {TAMTAM},
      title = {The number of cliques in graphs of given order and size},
      year = {2011},
      pages = {1599--1618},
      }
  • [Nost] Go to document E. A. Nordhaus and B. M. Stewart, "Triangles in an ordinary graph," Canad. J. Math., vol. 15, pp. 33-41, 1963.
    @ARTICLE{Nost, mrkey = {0151957},
      issn = {0008-414X},
      author = {Nordhaus, E. A. and Stewart, B. M.},
      mrclass = {55.10 (05.65)},
      doi = {10.4153/CJM-1963-004-7},
      journal = {Canad. J. Math.},
      zblnumber = {0115.17403},
      volume = {15},
      mrnumber = {0151957},
      fjournal = {Canadian Journal of Mathematics. Journal Canadien de Mathémetics},
      mrreviewer = {G. A. Dirac},
      title = {Triangles in an ordinary graph},
      year = {1963},
      pages = {33--41},
      }
  • [RazF] Go to document A. A. Razborov, "Flag algebras," J. Symbolic Logic, vol. 72, iss. 4, pp. 1239-1282, 2007.
    @ARTICLE{RazF, mrkey = {2371204},
      number = {4},
      issn = {0022-4812},
      author = {Razborov, Alexander A.},
      mrclass = {03C13},
      doi = {10.2178/jsl/1203350785},
      journal = {J. Symbolic Logic},
      zblnumber = {1146.03013},
      volume = {72},
      mrnumber = {2371204},
      fjournal = {Journal of Symbolic Logic},
      mrreviewer = {Manuel Bodirsky},
      coden = {JSYLA6},
      title = {Flag algebras},
      year = {2007},
      pages = {1239--1282},
      }
  • [RazT] Go to document A. A. Razborov, "On the minimal density of triangles in graphs," Combin. Probab. Comput., vol. 17, iss. 4, pp. 603-618, 2008.
    @ARTICLE{RazT, mrkey = {2433944},
      number = {4},
      issn = {0963-5483},
      author = {Razborov, Alexander A.},
      mrclass = {05C35},
      doi = {10.1017/S0963548308009085},
      journal = {Combin. Probab. Comput.},
      zblnumber = {1170.05036},
      volume = {17},
      mrnumber = {2433944},
      fjournal = {Combinatorics, Probability and Computing},
      mrreviewer = {Peter D. Johnson, Jr.},
      title = {On the minimal density of triangles in graphs},
      year = {2008},
      pages = {603--618},
      }
  • [SchTho] Go to document R. H. Schelp and A. Thomason, "A remark on the number of complete and empty subgraphs," Combin. Probab. Comput., vol. 7, iss. 2, pp. 217-219, 1998.
    @ARTICLE{SchTho, mrkey = {1617934},
      number = {2},
      issn = {0963-5483},
      author = {Schelp, Richard H. and Thomason, Andrew},
      mrclass = {05C35},
      doi = {10.1017/S0963548397003234},
      journal = {Combin. Probab. Comput.},
      zblnumber = {0908.05051},
      volume = {7},
      mrnumber = {1617934},
      fjournal = {Combinatorics, Probability and Computing},
      title = {A remark on the number of complete and empty subgraphs},
      year = {1998},
      pages = {217--219},
      }
  • [Turan] P. Turán, "Egy gráfelméleti szélsöertékfeladatról," Matematikai és Fizikai Lapok, vol. 48, pp. 436-451, 1941.
    @article{Turan, MRKEY={0018405},
      AUTHOR={Tur\'{a}n, P.},
      TITLE={Egy gr\'{a}felméleti szélsöertékfeladatról},
      JOURNAL={Matematikai és Fizikai Lapok},
      VOLUME={48},
      YEAR={1941},
      PAGES={436--451},
      MRNUMBER={0018405},
      ZBLNUMBER={0026.26903},
     }

Authors

Christian Reiher

Mathematisches Seminar der Universität Hamburg, Hamburg, Germany