UNIFORM TURAN DENSITY OF CYCLES

被引:2
作者
Bucic, Matija [1 ]
Cooper, Jacob W. [2 ]
Kral, Daniel [2 ]
Mohr, Samuel [2 ]
Correia, David Munha [3 ]
机构
[1] Princeton Univ, Inst Adv Study, Sch Math, Dept Math, Princeton, NJ 08540 USA
[2] Masaryk Univ, Fac Informat, Botanicka 68A, Brno 60200, Czech Republic
[3] Swiss Fed Inst Technol, Dept Math, CH-8092 Zurich, Switzerland
基金
欧洲研究理事会;
关键词
EXTREMAL PROBLEMS; NUMBER; HYPERGRAPHS; GRAPHS;
D O I
10.1090/tran/8873
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
In the early 1980s, Erdos and Sos initiated the study of the classical Turan problem with a uniformity condition: the uniform Turan density of a hypergraph H is the infimum over all d for which any sufficiently large hypergraph with the property that all its linear-size subhypergraphs have density at least d contains H. In particular, they raise the questions of determining the uniform Turan densities of K-4((3)-) and K-4((3)). The former question was solved only recently by Glebov, Kral', and Volec [Israel J. Math. 211 (2016), pp. 349-366] and Reiher, Rodl, and Schacht [J. Eur. Math. Soc. 20 (2018), pp. 1139-1159], while the latter still remains open for almost 40 years. In addition to K-4((3)-), the only 3-uniform hypergraphs whose uniform Turan density is known are those with zero uniform Turan density classified by Reiher, Rodl and Schacht [J. London Math. Soc. 97 (2018), pp. 77-97] and a specific family with uniform Turan density equal to 1/27. We develop new tools for embedding hypergraphs in host hypergraphs with positive uniform density and apply them to completely determine the uniform Turan density of a fundamental family of 3-uniform hypergraphs, namely tight cycles C-l((3)). The uniform Turan density of C-l((3)), l >= 5, is equal to 4/27 if l is not divisible by three, and is equal to zero otherwise. The case l = 5 resolves a problem suggested by Reiher.
引用
收藏
页码:4765 / 4809
页数:45
相关论文
共 38 条
[1]  
Alon Noga., 2004, PROBABILISTIC METHOD
[2]   Hypergraphs Do Jump [J].
Baber, Rahil ;
Talbot, John .
COMBINATORICS PROBABILITY & COMPUTING, 2011, 20 (02) :161-171
[3]  
Balogh J., 2022, J LOND MATH SOC, V481, P21
[4]   An upper bound for the Turan number t3(n, 4) [J].
Chung, F ;
Lu, LY .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1999, 87 (02) :381-389
[5]  
Conlon D, 2010, ELECTRON J COMB, V17
[6]   ON EXTREMAL PROBLEMS OF GRAPHS AND GENERALIZED GRAPHS [J].
ERDOS, P .
ISRAEL JOURNAL OF MATHEMATICS, 1964, 2 (03) :183-&
[7]   ON RAMSEY-TURAN TYPE THEOREMS FOR HYPERGRAPHS [J].
ERDOS, P ;
SOS, VT .
COMBINATORICA, 1982, 2 (03) :289-295
[8]   ON THE COMBINATORIAL PROBLEMS WHICH I WOULD MOST LIKE TO SEE SOLVED [J].
ERDOS, P .
COMBINATORICA, 1981, 1 (01) :25-42
[9]   ON THE STRUCTURE OF LINEAR GRAPHS [J].
ERDOS, P ;
STONE, AH .
BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1946, 52 (12) :1087-1091
[10]  
Erdos P., 1990, Algorithms Combin., V5, P12