Large $k$-cross-free families
Source: arxiv.org/abs/2611.26539
Two subsets $A,B$ of a finite set $X$ are crossing if $A\cap B$, $A\setminus B$, $B\setminus A$, and $X\setminus(A\cup B)$ are all nonempty. A family is $k$-cross-free if it contains no $k$ pairwise crossing members. We construct such families on $n$ elements of size $(\frac{1}{3}+o(1))kn\log k$, where the asymptotic is taken as $k$ tends to infinity and is uniform over all integers $n\ge k$. This disproves the uniform $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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.26539
curl -X POST /api/v1/records/arxiv/2611.26539/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.26539/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'