On local Turán problems
On local Turán problems
复制标题
关于图兰本地问题
DOI：
10.1016/j.jcta.2020.105329
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Rödl, Vojtěch
中科院分区：
文献类型：
--
作者：
Frankl, Peter;Huang, Hao;Rödl, Vojtěch
自提出以来，图兰超图问题一直是极值组合数学中最具挑战性的公开问题之一。其中之一是：给定n个顶点上的3-一致超图F，其中任意5个顶点跨越至少一条边，证明|F|≥(1/4−o(1))(N 3)。表明这个界限可能是最好的构造是简单的(X3)∪(Y3)，其中X和Y均匀地划分顶点集。这种构造具有以下更一般的(2p+1，p+1)-性质：任何2p+1个顶点的集合都跨越p+1个顶点上的一个完备子超图。我们的一个主要结果说，非常令人惊讶的是，对于所有p>；2，(2p+1，p+1)-性质蕴含着猜想的下界。
Since its formulation, Turán's hypergraph problems have been among the most challenging open problems in extremal combinatorics. One of them is the following: given a 3-uniform hypergraph F on n vertices in which any five vertices span at least one edge, prove that| F|≥(1/4− o (1))(n 3). The construction showing that this bound would be best possible is simply (X 3)∪(Y 3) where X and Y evenly partition the vertex set. This construction has the following more general (2 p+ 1, p+ 1)-property: any set of 2 p+ 1 vertices spans a complete sub-hypergraph on p+ 1 vertices. One of our main results says that, quite surprisingly, for all p> 2 the (2 p+ 1, p+ 1)-property implies the conjectured lower bound.