Article ID Journal Published Year Pages File Type
4655363 Journal of Combinatorial Theory, Series A 2014 19 Pages PDF
Abstract

A k-uniform linear cycle of length ℓ  , denoted by Cℓ(k), is a cyclic list of k  -sets A1,…,AℓA1,…,Aℓ such that consecutive sets intersect in exactly one element and nonconsecutive sets are disjoint. For all k⩾5k⩾5 and ℓ⩾3ℓ⩾3 and sufficiently large n we determine the largest size of a k  -uniform set family on [n][n] not containing a linear cycle of length ℓ  . For odd ℓ=2t+1ℓ=2t+1 the unique extremal family FSFS consists of all k  -sets in [n][n] intersecting a fixed t-set S   in [n][n]. For even ℓ=2t+2ℓ=2t+2, the unique extremal family consists of FSFS plus all the k-sets outside S   containing some fixed two elements. For k⩾4k⩾4 and large n we also establish an exact result for so-called minimal cycles  . For all k⩾4k⩾4 our results substantially extend Erdősʼs result on largest k  -uniform families without t+1t+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.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,