The VC‐Dimension of Random Subsets of Finite Groups
Authors:
Open Access
- 23 August 2026
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 69 (1) , e70089
Abstract
For a random subset of a finite group of cardinality , we consider the VC‐dimension of the family of its translates (equivalently the VC‐dimension of a random Cayley graph) and prove a law of large numbers as . This answers a question of McDonald–Sahay–Wyman.Keywords
All Related Versions
Funding Information
- Natural Sciences and Engineering Research Council of Canada
- American Mathematical Society
- Simons Foundation
- Purdue University
This publication has 24 references indexed in Scilit:
- Approximate subgroups with bounded VC-dimensionMathematische Annalen, 2022
- Erdős–Hajnal Conjecture for Graphs with Bounded VC-DimensionDiscrete & Computational Geometry, 2018
- Counting sets with small sumset and applicationsCombinatorica, 2015
- On covering by translates of a setRandom Structures & Algorithms, 2010
- Product set estimates for non-commutative groupsCombinatorica, 2008
- Counting Sets With Small Sumset, And The Clique Number Of Random Cayley GraphsCombinatorica, 2005
- Covering with blocks in the non-symmetric caseJournal of Theoretical Probability, 1995
- Random Cayley graphs and expandersRandom Structures & Algorithms, 1994
- On the waiting time till each of some given patterns occurs as a runProbability Theory and Related Fields, 1991
- Quasi-random graphsCombinatorica, 1989