Hypergraph regularity and higher arity VC-dimension

2020/10/01 by Chernikov, Artem, Towsner, Henry · 4 citations
#03C45 #05C35 #05C55 #05C65 #05C75 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO)

paper · doi:10.48550/arxiv.2010.00726

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

Cited by

• Remarks on a recent preprint of Chernikov and Towsner
• On the quadratic complexity of subsets of \mathbbF_pⁿ of bounded \mathrmVC₂-dimension
• Higher-arity PAC learning, VC dimension and packing lemma
• Regularity for hypergraphs with bounded VC₂ dimension

Related

• Regularity for hypergraphs with bounded VC₂ dimension
• A Tight Bound for Hypergraph Regularity II
• Regularity inheritance in hypergraphs
• Induced subgraph density. VI. Bounded VC-dimension
• A Tight Bound for Hyperaph Regularity