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

CREATORLior Gishboliner, Asaf Shapira, Yuval Wigderson
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE163 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-09969

Browse the full library · About the Tower of Babel