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 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 . 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 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 等数据库收录! |
|