The VC-dimension of random subsets of finite groups

DOI10.1002/RSA.70089MaRDI QIDQ7325297zbMATH OpenFDO

Authors Brad Rodgers, Anurag Sahay

Publication date 7 September 2026

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1002/RSA.70089

Mathematics Subject Classification ID

Classification theory, stability, and related concepts in model theory (03C45) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Number theory (11-XX)

Cites work

• A semi-algebraic version of Zarankiewicz's problem
• Approximate subgroups with bounded VC-dimension
• Bounded VC-dimension implies the Schur-Erdős conjecture
• Convolutions of sets with bounded VC-dimension are uniformly continuous
• Counting sets with small sumset and applications
• Counting sets with small sumset, and the clique number of random Cayley graphs
• Covering with blocks in the non-symmetric case
• Efficient arithmetic regularity and removal lemmas for induced bipartite patterns
• Erdős-Hajnal conjecture for graphs with bounded VC-dimension
• Extractors in Paley graphs: a random model
• High-dimensional probability. An introduction with applications in data science
• scientific article; zbMATH DE number 3167451 (Why is no real title available?)
• Improved incidence bounds over arbitrary finite fields via the VC-dimension theory
• On covering by translates of a set
• On subgraphs of random Cayley sum graphs
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• On the waiting time till each of some given patterns occurs as a run
• Product set estimates for non-commutative groups
• Quasi-random graphs
• Random Cayley graphs and expanders
• Stable arithmetic regularity in the finite field model
• Structure and regularity for subsets of groups with finite VC-dimension
• The chromatic number of random Cayley graphs
• The Generalised Coupon Collector Problem
• The Vapnik-Chervonenkis dimension of a random graph
• The VC dimension of quadratic residues in finite fields
• Understanding machine learning. From theory to algorithms
• VC-dimension and pseudo-random graphs
• VC-dimension of sets of permutations
• VC-dimensions of random function classes

This page was built for publication: The VC-dimension of random subsets of finite groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7325297)