betaFeedback

WorksMathematics

Large kk-cross-free families

Abstract

Two subsets A,BA,B of a finite set XX are crossing if A∩BA\cap B, A∖BA\setminus B, B∖AB\setminus A, and X∖(A∪B)X\setminus(A\cup B) are all nonempty. A family is kk-cross-free if it contains no kk pairwise crossing members. We construct such families on nn elements of size (13+o(1))knlog⁡k(\frac{1}{3}+o(1))kn\log k, where the asymptotic is taken as kk tends to infinity and is uniform over all integers n≥kn\ge k. This disproves the uniform O(kn)O(kn) 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 O(knlog⁡k)O(kn\log k) upper bound for kk-cross-free families closed under all cyclic shifts of a fixed cyclic ordering of the ground set.

Paper details

vlnc:W_3p7q8tqp
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…