WorksMathematics
Large -cross-free families
Abstract
Two subsets of a finite set are crossing if , , , and are all nonempty. A family is -cross-free if it contains no pairwise crossing members. We construct such families on elements of size , where the asymptotic is taken as tends to infinity and is uniform over all integers . This disproves the uniform bound conjectured by Karzanov and Lomonosov. Our construction consists of cyclic intervals with at most one point deleted, together with their complements. We also prove an upper bound for -cross-free families closed under all cyclic shifts of a fixed cyclic ordering of the ground set.