The VC‐Dimension of Random Subsets of Finite Groups

Random Structures and Algorithms 2026 Open access

Read full text
Authors: Brad Rodgers, Anurag Sahay
DOI: 10.1002/rsa.70089
Cited by: 0

Abstract

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.

Fields of Study & Subjects

Advanced Topology and Set Theory Finite Group Theory Research Computability Logic AI Algorithms

Publication details

Journal / source
Random Structures and Algorithms
Volume
69
Issue
1
Publication date
1 August 2026
Language
EN