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

CREATORTing-Wei Chao, Zixiang Xu, Chi Hoi Yip, Shengtong Zhang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE75 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-13850

Browse the full library · About the Tower of Babel