The Library
The maximum size of hypergraphs without generalized 4-cycles
Tools
Pikhurko, Oleg and Verstraëte, Jacques (2009) The maximum size of hypergraphs without generalized 4-cycles. Journal of Combinatorial Theory, Series A, Vol.116 (No.3). pp. 637-649. doi:10.1016/j.jcta.2008.09.002 ISSN 0097-3165.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/j.jcta.2008.09.002
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→∞.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | Journal of Combinatorial Theory, Series A | ||||
Publisher: | Academic Press | ||||
ISSN: | 0097-3165 | ||||
Official Date: | April 2009 | ||||
Dates: |
|
||||
Volume: | Vol.116 | ||||
Number: | No.3 | ||||
Page Range: | pp. 637-649 | ||||
DOI: | 10.1016/j.jcta.2008.09.002 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |