Beating the Ahlswede--Khachatrian bound for the Erdős--Frankl--Pach problem
In the 1980s, Erdős and, independently, Frankl and Pach conjectured that, for sufficiently large $n$, every $(d+1)$-uniform family on $\{1,\ldots,n\}$ with VC-dimension $d$ has size at most $\binom{n-1}{d}$, the size of a star. Ahlswede and Khachatrian disproved this conjecture in 1997 by giving a family of size $\binom{n-1}{d}+\binom{n-4}{d-2}$. This value has since been widely believed to be best possible, and Mubayi and Zhao explicitly conjectured its optimality in 2007. Very recently, Wang, Xu and Zhang proved their conjecture for $d=2$ and $n\ge 7$, providing further support for this…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.23469
curl -X POST /api/v1/records/arxiv/2606.23469/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.23469/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'