The maximum size of hypergraphs without generalized 4-cycles
The maximum size of hypergraphs without generalized 4-cycles
复制标题
无广义 4 循环的超图的最大尺寸
DOI：
10.1016/j.jcta.2008.09.002
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Jacques Verstraëte
中科院分区：
文献类型：
--
作者：
O. Pikhurko;Jacques Verstraëte
设fr（n）是n阶r-一致超图中不包含4条不同边A，B，C，D且A <$B=C <$D且A <$B=C <$D= N的最大边数.这个问题是由Erdés [P. Erdés，组合分析中的问题和结果，Congr. Numer. 19（1977）3-12]。它可以被看作是4圈图的图兰问题到超图的推广。设nr =lim supn→∞fr（n）/（nr−1）。Füredi [Z. Füredi，Hypergraphs in which all disjoint pairs have distinct unions，Combinatorica 4（1984）161-168]观察到，对于每个r <$3，这是相等的。Mubayi和Verstraëte [D. Mubayi，J. Verstraëte，二分图兰问题的超图扩展，J. Combin。理论系列A 106（2004）237-253]。在这里，我们改进了这个边界。也就是说，我们证明了对于每一个r <$3和<$3 <$13/9，<$r <$min（7/4，1 +2/r）。特别地，当r→∞时，则可得出Δ r→1。
Let fr(n) be the maximum number of edges in an r-uniform hypergraph on n vertices that does not contain four distinct edges A, B, C, D with A∪B=C∪D and A∩B=C∩D=∅. This problem was stated by Erdős [P. Erdős, Problems and results in combinatorial analysis, Congr. Numer. 19 (1977) 3–12]. It can be viewed as a generalization of the Turán problem for the 4-cycle to hypergraphs. Let ϕr=lim supn→∞fr(n)/(nr−1). Füredi [Z. Füredi, Hypergraphs in which all disjoint pairs have distinct unions, Combinatorica 4 (1984) 161–168] observed that ϕr⩾1 and conjectured that this is equality for every r⩾3. The best known upper bound ϕr⩽3 was proved by Mubayi and Verstraëte [D. Mubayi, J. Verstraëte, A hypergraph extension of the bipartite Turán problem, J. Combin. Theory Ser. A 106 (2004) 237–253]. Here we improve this bound. Namely, we show that ϕr⩽min(7/4,1+2/r) for every r⩾3, and ϕ3⩽13/9. In particular, it follows that ϕr→1 as r→∞.