THE EXACT MINIMUM NUMBER OF TRIANGLES IN GRAPHS WITH GIVEN ORDER AND SIZE
THE EXACT MINIMUM NUMBER OF TRIANGLES IN GRAPHS WITH GIVEN ORDER AND SIZE
复制标题
给定顺序和大小的图中三角形的确切最小数量
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Katherine Staden
中科院分区：
文献类型：
--
作者：
Hong Liu;O. Pikhurko;Katherine Staden
在一个给定顺序和大小的图中，三角形的最小数目是多少？受Mantel和Turán早期结果的启发，Rademacher在1941年解决了这个问题的第一个不平凡的案例。这个问题在1955年由ErdőS重新提出，现在被称为ErdőS-Rademacher问题。在引起广泛关注后，拉兹博罗夫在2008年取得了重大突破，渐进地解决了这个问题。本文给出了边密度在$1范围内的所有大型图的精确解，并在此范围内证实了Lovász和Simonovits自1975年以来的一个猜想。此外，我们还给出了极图的一个刻画。
What is the minimum number of triangles in a graph of given order and size? Motivated by earlier results of Mantel and Turán, Rademacher solved the first nontrivial case of this problem in 1941. The problem was revived by Erdős in 1955; it is now known as the Erdős–Rademacher problem. After attracting much attention, it was solved asymptotically in a major breakthrough by Razborov in 2008. In this paper, we provide an exact solution for all large graphs whose edge density is bounded away from $1$, which in this range confirms a conjecture of Lovász and Simonovits from 1975. Furthermore, we give a description of the extremal graphs.