McDonald–Sahay–Wyman's conjecture on the VC-dimension of Paley graphs
McDonald–Sahay–Wyman's conjecture on the VC-dimension of Paley graphs
Let be prime, and let be the Paley (di)graph on . The VC-dimension is the maximum cardinality of a set shattered by the neighborhoods of .
McDonald–Sahay–Wyman's conjecture. As through the primes,
This conjecture is motivated by the analogous asymptotic behavior of random Cayley graphs and by the pseudorandomness of Paley graphs. The source mentions partial progress and numerical evidence, but does not state a resolution.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Brad Rodgers and Anurag Sahay, “The VC-dimension of random subsets of finite groups”, arXiv:2506.14219 (2025).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.