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

Research output not available from this repository, contact author.

Request Changes to record.

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 > Mathematics
Journal or Publication Title:	Journal of Combinatorial Theory, Series A
Publisher:	Academic Press
ISSN:	0097-3165
Official Date:	April 2009
Dates:	Date Event April 2009 Published
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