Pith. sign in

REVIEW 3 cited by

Hypergraph regularity and higher arity VC-dimension

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2010.00726 v1 pith:IRBWV4QV submitted 2020-10-01 math.CO cs.DMmath.LO

Artem Chernikov , Henry Towsner This is my paper
classification math.COcs.DMmath.LO
keywords hypergraphsetsk-dimensionregularitysmalluniformapproximatedclose
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

We generalize the fact that graphs with small VC-dimension can be approximated by rectangles, showing that hypergraphs with small VC_k-dimension (equivalently, omitting a fixed finite (k+1)-partite (k+1)-uniform hypergraph) can be approximated by k-ary cylinder sets. In the language of hypergraph regularity, this shows that when H is a k'-uniform hypergraph with small VC_k-dimension for some k<k', the decomposition of H given by hypergraph regularity only needs the first k levels---one can approximate H using sets of vertices, sets of pairs, and so on up to sets of k-tuples---and that on most of the resulting k-ary cylinder sets, the density of H is either close to 0 or close to 1. We also show a suitable converse: k'-uniform hypergraphs with large VC_k-dimension cannot have such approximations uniformly under all measures on the vertices.

Discussion (0). Sign in to comment.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Regularity for hypergraphs with bounded VC$_2$ dimension

    math.CO 2025-08 accept novelty 8.0 of 10

    For 3-graphs of bounded VC2 dimension, an (ε,ψ)-regular partition exists with twr(twr(poly(1/ε))) vertex parts, improving the generic wowzer bound to tower type.

  2. Averages of hypergraphs and higher arity stability

    math.CO 2025-08 conditional novelty 8.0 of 10

    Functions built from intersections of set families satisfy a strong hypergraph regularity lemma, and the two known sources of ternary instability both satisfy this regularity, so strong 2-stability cannot be defined b...

  3. Homogeneous hypergraph regularity lemmas via $k$-strong honest definitions

    math.LO 2026-07 conditional novelty 6.0 of 10

    (k+1)-uniform hypergraphs definable in NIP strongly k-distal structures admit homogeneous regularity lemmas whose partitions are uniformly definable and polynomially bounded in 1/δ.

Pith tools