The VC-dimension of random subsets of finite groups

Brad Rodgers, Anurag Sahay

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)…