Uniform set systems with small VC-dimension
Ting-Wei Chao, Zixiang Xu, Chi Hoi Yip, Shengtong Zhang · 2025
Read Uniform set systems with small VC-dimension by Ting-Wei Chao, Zixiang Xu, Chi Hoi Yip, Shengtong Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-13850.txt.
Description
Ting-Wei Chao and three colleagues present a 2025 combinatorics paper attacking a bound that had barely moved in forty years. The question: how large can a family of equal-sized sets be if its VC-dimension, a measure of the patterns it can realize, stays small? A 1984 argument capped such families at a clean binomial bound, but constructions fell well short, and later gains were tiny.
The authors' purely combinatorial method strips away the main term of the gap for large cases, nearly closing the distance between the best construction and the cap. They also revisit a related old conjecture, recently disproven, and propose a refined version they hope can stand, verifying several of its cases. The result reframes what small VC-dimension forces on a set family.
Catalog record
| CREATOR | Ting-Wei Chao, Zixiang Xu, Chi Hoi Yip, Shengtong Zhang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 75 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-13850