On the Turán number of Triple-Systems
On the Turán number of Triple-Systems
复制标题
关于三重系统的图兰数
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
V. Rödl
中科院分区：
文献类型：
--
作者：
D. Mubayi;V. Rödl
对于 r-图族 F ，图兰数 ex(n,F) 是不包含 F 任何成员的 n 顶点 r-图中边的最大数量。图兰密度 π(F) = lim n→∞ ex(n,F) ( n r ) 。当 F 是 r 图、π(F) 6= 0 且 r > 2 时，确定 π(F) 是一个众所周知的难题，即使对于非常简单的 r 图 F 也是如此。例如，当 r = 3 时，对于极少数 (< 10) 不可约 r 图，π(F) 的值是已知的。基于 de Caen 和 Füredi 最近开发的方法 [3]，我们确定了几个以前未知的 3 图的 Turán 密度。使用这种方法，我们还给出了 Frankl 和 Füredi [5] 结果的新证明，即 π(H) = 2/9，其中 H 的边为 123, 124, 345。令 F(3, 2) 为 3-图 123, 145, 245, 345，令 K− 4 为 3-图 123, 124, 234，并令C5 是 3 图 123, 234, 345, 451, 512。我们证明 • 4/9 ≤ π(F(3, 2)) ≤ 1/2， • π({K− 4 , C5}) ≤ 10/31 = 0.322581， • 0.464 < π(C5) ≤ 2− √ 2 < 0.586。中间的结果与 Frankl 和 Füredi [6] 的猜想 π(K− 4 ) = 2/7 有关。最著名的界限是 2/7 ≤ π(K− 4 ) ≤ 1/3。 *佐治亚理工学院数学学院，亚特兰大，GA 30332-0160，美国；研究部分由美国国家科学基金会 DMS-9970325 资助 †Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA；研究部分由国家科学基金会资助 DMS-0071261 1991 数学学科分类：05C35、05C65、05D05
For a family of r-graphs F , the Turán number ex(n,F) is the maximum number of edges in an n vertex r-graph that does not contain any member of F . The Turán density π(F) = lim n→∞ ex(n,F) ( n r ) . When F is an r-graph, π(F) 6= 0, and r > 2, determining π(F) is a notoriously hard problem, even for very simple r-graphs F . For example, when r = 3, the value of π(F) is known for very few (< 10) irreducible r-graphs. Building upon a method developed recently by de Caen and Füredi [3], we determine the Turán densities of several 3-graphs that were not previously known. Using this method, we also give a new proof of a result of Frankl and Füredi [5] that π(H) = 2/9, where H has edges 123, 124, 345. Let F(3, 2) be the 3-graph 123, 145, 245, 345, let K− 4 be the 3-graph 123, 124, 234, and let C5 be the 3-graph 123, 234, 345, 451, 512. We prove • 4/9 ≤ π(F(3, 2)) ≤ 1/2, • π({K− 4 , C5}) ≤ 10/31 = 0.322581, • 0.464 < π(C5) ≤ 2− √ 2 < 0.586. The middle result is related to a conjecture of Frankl and Füredi [6] that π(K− 4 ) = 2/7. The best known bounds are 2/7 ≤ π(K− 4 ) ≤ 1/3. ∗School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332-0160, USA; research supported in part by the National Science Foundation under grant DMS-9970325 †Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA; research supported in part by the National Science Foundation under grant DMS-0071261 1991 Mathematics Subject Classification: 05C35, 05C65, 05D05