Discrepancy versus Spectral Expansion in Sparse Regular Graphs

Definitions and mathematical statement

The supplied problem concerns an asymptotic family of regular graphs. For a precise provisional formulation, use the convention that graphs are finite, simple, and undirected; the source record does not explicitly specify this convention.

Let $(G_k)_{k\geq 1}$ be a sequence of such graphs, where $G_k=(V_k,E_k)$ is $d_k$-regular, $n_k=|V_k|\to\infty$, $d_k>0$, and $d_k/n_k\to 0$. No assumption that $d_k\to\infty$ is supplied. Write $A_k$ for the adjacency matrix and $\mathbf{1}_k$ for the all-ones vector. For arbitrary, possibly overlapping sets $S,T\subseteq V_k$, define \[ e_k(S,T)=\sum_{u\in S}\sum_{v\in T}(A_k)_{uv}. \] Thus an edge with both endpoints in $S\cap T$ contributes twice. Interpret the discrepancy hypothesis uniformly over vertex sets as \[ \Delta_k:=\max_{S,T\subseteq V_k} \left|e_k(S,T)-\frac{d_k|S||T|}{n_k}\right|, \qquad \frac{\Delta_k}{n_kd_k}\longrightarrow 0. \] Since $A_k\mathbf{1}_k=d_k\mathbf{1}_k$, the subspace $\mathbf{1}_k^\perp$ is invariant under $A_k$. Define \[ \lambda_*(G_k)=\max\left\{|\lambda|:\lambda\text{ is an eigenvalue of }A_k|_{\mathbf{1}_k^\perp}\right\}. \] Here only the constant-vector eigenvalue is excluded: additional occurrences of $d_k$, and the eigenvalue $-d_k$ if present, are included.

Question under these conventions. Must every sequence satisfying the preceding hypotheses satisfy \[ \frac{\lambda_*(G_k)}{d_k}\longrightarrow 0? \] The uniform interpretation of the error, the edge-counting convention for overlapping sets, and the meaning of "nontrivial" eigenvalues require confirmation against the original source. The supplied record does not impose connectedness, nonbipartiteness, vertex transitivity, or a Cayley graph structure. Its open-problem label and its claim of prior statement verification are supplied editorial assessments, not mathematical verification of this draft.

Short English statement

For sparse regular graphs, does uniformly small absolute discrepancy between all pairs of vertex sets force every adjacency eigenvalue orthogonal to the constant vector to be small compared with the degree? The draft makes the asymptotic quantifiers explicit, but the graph, edge-counting, and eigenvalue conventions require source confirmation.

Sources

• Local registry: data/unsolvedmath/problems.json, supplied record with permanent UnsolvedMath ID $30003128$, title "Discrepancy versus Spectral Expansion in Sparse Regular Graphs," and exact source problem code catalogue entry. The record belongs to the Oberwolfach Reports Open Problems collection. No individual proposer is supplied; the proposed year is recorded as 2016.
• Supplied report citation: Combinatorics and Probability (2017), Oberwolfach Reports, DOI 10.4171/owr/2016/22, pp. 1189--1257. https://doi.org/10.4171/owr/2016/22. The supplied background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions. The citation's 2017 label differs from the proposed year and the year appearing in the DOI; this discrepancy has not been resolved.
• Conlon and Zhao, Quasirandom Cayley Graphs, supplied literature reference: https://arxiv.org/abs/1603.03025.
• Conlon and Zhao, "Published Version," supplied literature reference: https://doi.org/10.19086/da.1294.
• Literature assessment dated exactly 2026-08-21: the supplied curation labels the problem open and states that the general discrepancy--spectral equivalence for sparse graphs is unsettled in the stated broad form, while Conlon and Zhao establish a strong converse for Cayley and vertex-transitive graphs rather than arbitrary sparse graphs. This is supplied dated curation derived from the OWR record, not independently verified here; both the time-sensitive status and the cited claims require independent checking.
• The registry labels the statement corrected_verified and reports a prior manual semantic, typographic, and LaTeX review. These are supplied provenance claims and do not constitute mathematical review of the present statement-only draft. No cited source has been visited for this preparation.