Regularity for hypergraphs with bounded VC 2 dimension
Lior Gishboliner, Asaf Shapira, Yuval Wigderson · 2025
Read Regularity for hypergraphs with bounded VC 2 dimension by Lior Gishboliner, Asaf Shapira, Yuval Wigderson (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-2508-09969.txt.
Description
Lior Gishboliner, Asaf Shapira, and Yuval Wigderson sharpen split bounds for hypergraph regularity under a weak dimension cap, in a paper from two thousand twenty-five. The classic split lemma can force tower-size parts, and hypergraph versions fare worse. A weak, natural dimension notion raised an open question for triple systems.
Under the cap, the bound drops one level in the Ackermann scale, and no better drop is possible. A new proof route starts from a cylinder split lemma for plain graphs of capped dimension. A hypergraph form of that lemma carries the method up. Side uses of the cylinder tool are flagged too. Readers get a rare case where huge bounds truly shrink.
Catalog record
| CREATOR | Lior Gishboliner, Asaf Shapira, Yuval Wigderson |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 163 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-09969