Delphi.science

Large $k$-cross-free families

Source: arxiv.org/abs/2611.26539

Jack H. Koolen, Anyuan Tian

arXivarxiv/2611.26539Nov 19, 2026math.COscore 0

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…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

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}'