首页 | 本学科首页   官方微博 | 高级检索  
     检索      


The maximum size of hypergraphs without generalized 4-cycles
Authors:Oleg Pikhurko  Jacques Verstraëte
Institution:a Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, USA
b Department of Mathematics, University of California, San Diego, La Jolla, CA 92093, USA
Abstract: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 AB=CD and AB=CD=∅. 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 View the MathML source. 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 View the MathML source for every r?3, and ?3?13/9. In particular, it follows that ?r→1 as r→∞.
Keywords:Generalized 4-cycle  Turá  n function
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号