McDonald–Sahay–Wyman's conjecture on the VC-dimension of Paley graphs

About 1 year old · traced to

Let NN be prime, and let b[?2004lΓ=Γ(N)b[?2004l\Gamma=\Gamma(N) be the Paley (di)graph on Z/NZ\mathbb{Z}/N\mathbb{Z}. The VC-dimension VCdim⁡(Γ)\operatorname{VCdim}(\Gamma) is the maximum cardinality of a set shattered by the neighborhoods of Γ\Gamma.

McDonald–Sahay–Wyman's conjecture. As N→∞N\to\infty through the primes,

VCdim⁡(Γ)=(1+o(1))log⁡2N.\operatorname{VCdim}(\Gamma)=(1+o(1))\log_2 N.

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.