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.
References
Primary source
Brad Rodgers and Anurag Sahay, “The VC-dimension of random subsets of finite groups”, arXiv:2506.14219 (2025).
Progress summary
Never refreshed
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.