The VC-dimension of random subsets of finite groups
Preprint
Abstract
For a random subset of a finite group $G$ of cardinality $N$, 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 $N\rightarrow\infty$. This answers a question of McDonald--Sahay--Wyman.
Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- VC-dimension and pseudo-random graphsDiscrete Applied Mathematics, 2025
- The VC dimension of quadratic residues in finite fieldsDiscrete Mathematics, 2024
- Approximate subgroups with bounded VC-dimensionMathematische Annalen, 2022
- Extractors in Paley graphs: A random modelEuropean Journal of Combinatorics, 2016
- Counting sets with small sumset and applicationsCombinatorica, 2015
- The chromatic number of random Cayley graphsEuropean Journal of Combinatorics, 2013
- Counting Sets With Small Sumset, And The Clique Number Of Random Cayley GraphsCombinatorica, 2005
- The vapnik-chervonenkis dimension of a random graphDiscrete Mathematics, 1995
- Random Cayley graphs and expandersRandom Structures & Algorithms, 1994
- Quasi-random graphsCombinatorica, 1989