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

From papers

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 NN\to\infty through the primes,

VCdim(Γ)=(1+o(1))log2N.\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.

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

No solutions have been posted yet.