Hypergraph Turán numbers of linear cycles

Füredi, Zoltán and Jiang, Tao (2014) Hypergraph Turán numbers of linear cycles. JOURNAL OF COMBINATORIAL THEORY SERIES A, 123 (1). pp. 252-270. ISSN 0097-3165

Preview

Text 1302.2387.pdf Download (199kB) | Preview

Abstract

A k-uniform linear cycle of length ℓ, denoted by Cℓ(k), is a cyclic list of k-sets A1, . . . , Aℓ such that consecutive sets intersect in exactly one element and nonconsecutive sets are disjoint. For all k ≥ 5 and ℓ ≥ 3 and sufficiently large n we determine the largest size of a k-uniform set family on [n] not containing a linear cycle of length ℓ. For odd ℓ = 2t + 1 the unique extremal family FS consists of all k-sets in [n] intersecting a fixed t-set S in [n]. For even ℓ = 2t + 2, the unique extremal family consists of FS plus all the k-sets outside S containing some fixed two elements. For k ≥ 4 and large n we also establish an exact result for so-called minimal cycles. For all k ≥ 4 our results substantially extend Erdos's result on largest k-uniform families without t + 1 pairwise disjoint members and confirm, in a stronger form, a conjecture of Mubayi and Verstraëte. Our main method is the delta system method. © 2014 Elsevier Inc.

Actions (login required)

Edit Item