论文标题
在Ramsey-Turán的三角形密度上
On the Ramsey-Turán density of triangles
论文作者
论文摘要
由于壁炉架，现代图理论中最古老的结果之一就是断言，$ n $ vertices上的每个无三角形图最多都有$ \ lfloor n^2/4 \ rfloor $ edges。大约半个世纪后，安德拉斯法（Andrásfai）研究了无三角形的图形，并证明了$ n $顶点上最大的三角形图，没有独立尺寸$αn$的独立集，其中$ 2/5 \ leα<1/2 $，是五角大楼的爆炸。自安德拉斯法（Andrásfai）的工作以来，已经过去了50多年。在本文中，我们迈出了下一步，迈向理解无三角形图的结构而没有大型独立集。 值得注意的是，我们确定了$ n $顶点的最大三角形图〜$ g $，$ n $顶点，$α（g）\ ge 3n/8 $，并在$α（g）> n/3 $的结构上指出了猜想。我们指出的是，$α（g）\ le n/3 $的行为方式有所不同，但是由于布兰特的工作，这种情况得到了充分的理解。
One of the oldest results in modern graph theory, due to Mantel, asserts that every triangle-free graphs on $n$ vertices has at most $\lfloor n^2/4\rfloor$ edges. About half a century later Andrásfai studied dense triangle-free graphs and proved that the largest triangle-free graphs on $n$ vertices without independent sets of size $αn$, where $2/5\le α< 1/2$, are blow-ups of the pentagon. More than 50 further years have elapsed since Andrásfai's work. In this article we make the next step towards understanding the structure of dense triangle-free graphs without large independent sets. Notably, we determine the maximum size of triangle-free graphs~$G$ on $n$ vertices with $α(G)\ge 3n/8$ and state a conjecture on the structure of the densest triangle-free graphs $G$ with $α(G) > n/3$. We remark that the case $α(G) \le n/3$ behaves differently, but due to the work of Brandt this situation is fairly well understood.
