×

The clique density theorem. (English) Zbl 1348.05103

Summary: 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, L. Lovász and M. Simonovits [in: Studies in pure mathematics. To the memory of Paul Turán. Basel-Boston-Stuttgart: Birkhäuser Verlag; Budapest: Akademiai Kiado. 459–495 (1983; Zbl 0519.05042)] 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 A. A. Razborov [Comb. Probab. Comput. 17, No. 4, 603–618 (2008; Zbl 1170.05036)] and for \(r=4\) by V. Nikiforov [Trans. Am. Math. Soc. 363, No. 3, 1599–1618 (2011; Zbl 1231.05129)]. In this article, we prove the conjecture for all values of \(r\).

MSC:

05C35 Extremal problems in graph theory
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C42 Density (toughness, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] B. Bollobás, ”Relations between sets of complete subgraphs,” in Proceedings of the Fifth British Combinatorial Conference, Winnipeg, Man., 1976, pp. 79-84. · Zbl 0325.05118
[2] P. Csikvári, ”Note on the smallest root of the independence polynomial,” Combin. Probab. Comput., vol. 22, iss. 1, pp. 1-8, 2013. · Zbl 1257.05066 · doi:10.1017/S0963548312000302
[3] D. C. Fisher, ”Lower bounds on the number of triangles in a graph,” J. Graph Theory, vol. 13, iss. 4, pp. 505-512, 1989. · Zbl 0673.05046 · doi:10.1002/jgt.3190130411
[4] 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. · Zbl 1339.05231 · doi:10.1016/S0020-0190(00)00086-7
[5] A. W. Goodman, ”On sets of acquaintances and strangers at any party,” Amer. Math. Monthly, vol. 66, pp. 778-783, 1959. · Zbl 0092.01305 · doi:10.2307/2310464
[6] N. G. Hadvziivanov and V. S. Nikiforov, ”The Nordhaus-Stewart-Moon-Moser inequality,” Serdica, vol. 4, iss. 4, pp. 344-350, 1978. · Zbl 0475.05051
[7] 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. · Zbl 0519.05042
[8] 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. · Zbl 0114.01206
[9] 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. · Zbl 1231.05129 · doi:10.1090/S0002-9947-2010-05189-X
[10] E. A. Nordhaus and B. M. Stewart, ”Triangles in an ordinary graph,” Canad. J. Math., vol. 15, pp. 33-41, 1963. · Zbl 0115.17403 · doi:10.4153/CJM-1963-004-7
[11] A. A. Razborov, ”Flag algebras,” J. Symbolic Logic, vol. 72, iss. 4, pp. 1239-1282, 2007. · Zbl 1146.03013 · doi:10.2178/jsl/1203350785
[12] A. A. Razborov, ”On the minimal density of triangles in graphs,” Combin. Probab. Comput., vol. 17, iss. 4, pp. 603-618, 2008. · Zbl 1170.05036 · doi:10.1017/S0963548308009085
[13] 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. · Zbl 0908.05051 · doi:10.1017/S0963548397003234
[14] P. Turán, ”Egy gráfelméleti szélsöertékfeladatról,” Matematikai és Fizikai Lapok, vol. 48, pp. 436-451, 1941. · Zbl 0026.26903
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.