Independent Sets in Pseudorandom Regular Graphs

Definitions and mathematical statement

Under the standard convention, an $(n,d,\lambda)$-graph is a finite simple undirected $d$-regular graph $G$ on $n$ vertices such that every eigenvalue of its adjacency matrix restricted to the orthogonal complement of the all-ones vector has absolute value at most $\lambda$. This convention is not explicitly defined in the supplied record and requires confirmation against the report. Here $n\geq 2$, $d\in\{0,\ldots,n-1\}$, and $\lambda\geq0$. We interpret $\log$ as the natural logarithm, and $e$ denotes its base; the logarithm convention also requires source confirmation.

For an integer $k\geq0$, define the number of independent $k$-vertex sets by \[ i_k(G)=\left|\left\{S\subseteq V(G): |S|=k,\ E(G[S])=\varnothing\right\}\right|. \] The supplied question asks whether there exists an absolute constant $C>0$, independent of all graph parameters, such that every $(n,d,\lambda)$-graph with \[ \lambda>(\log n)^2 \] satisfies the proposed bound \[ i_t(G)\leq\left(\frac{4e^2\lambda}{\log n}\right)^t, \qquad t=\frac{Cn\log n}{d+1}. \] There is an unresolved integrality qualification: the right-hand expression defining $t$ need not be an integer, whereas $i_t(G)$ as defined above requires an integer index. The display is meaningful directly whenever this value is integral. The record does not specify rounding, a range of integer sizes, or a restriction to parameters giving integral $t$. No such repair is imposed here; a fully quantified formulation requires that choice to be recovered from the source. The record also does not explicitly state an asymptotic lower bound on $n$.

The following contextual claims are supplied source commentary, not independently verified results in this draft. The question is described as an improvement on the report's Theorem 15, associated in the supplied assessment with an Alon--Rodl estimate at a larger logarithmic threshold. The theorem's precise statement is not supplied. The original excerpt credits Mubayi and Verstraete, reference [3], with observing that Theorem 15, through sampling from a suitable $C_4$-free graph, gives a lower bound $\Omega(s^{3/2}/\log s)$ for $r(C_4,s)$, matching the stated result of the $C_4$-free process. Here $C_k$ denotes a cycle of length $k$, and $r(C_k,s)$, also written $R(C_k,s)$, denotes the least $N$ such that every graph on $N$ vertices contains $C_k$ as a subgraph or an independent set of size $s$; the $\Omega$ notation expresses an asymptotic lower bound up to a positive constant as $s\to\infty$.

The excerpt further states that a positive answer to its Question 16 would yield a quick proof of $R(C_3,s)\geq\Omega(s^2/\log s)$ by sampling from optimally pseudorandom triangle-free graphs attributed to Alon, reference [1], and would improve some even-cycle versus complete-graph Ramsey bounds by logarithmic factors. It states that random $d$-regular graphs force $C\geq2$, that the proposed bound holds for random $d$-regular graphs, and asks additionally whether it can be proved for specific $(n,d,\lambda)$-graphs. Parameter regimes and probabilistic quantifiers for these random-graph assertions are not supplied, so these assertions are retained as qualified contextual claims rather than fully formulated subsidiary theorems.

Short English statement

The question asks for one universal constant $C>0$ bounding the number of independent sets of size approximately $Cn\log n/(d+1)$ in every regular graph satisfying the stated spectral condition. The exact size convention is unresolved because the displayed size need not be integral. The supplied curation labels the problem open; this draft does not independently verify that status.

Sources

• Local UnsolvedMath registry, permanent ID $30006564$, title Independent Sets in Pseudorandom Regular Graphs, exact source code catalogue entry. The record assigns proposed year 2026 and supplies no named proposer.
• Combinatorics (2026), Oberwolfach Reports, DOI 10.4171/owr/2026/1, pp. 5--79: https://doi.org/10.4171/owr/2026/1. This is the report citation supplied for the question and its surrounding workshop discussion; it is also listed among the supplied literature sources as Oberwolfach Report 1/2026. The excerpt refers to Theorem 15 and Question 16 without supplying a precise location within these pages.
• Mubayi--Verstraete, A note on pseudorandom Ramsey graphs: https://doi.org/10.4171/JEMS/1359. This supplied literature source accompanies the excerpt's attribution to Mubayi and Verstraete, reference [3]. The complete numbered bibliography is not supplied, so the correspondence of that reference number has not been independently checked.
• The excerpt attributes the optimally pseudorandom triangle-free construction to Alon, reference [1], without providing the bibliographic entry or a link. The assessment names an Alon--Rodl estimate without a separate complete citation.
• Literature assessment dated 2026-08-22: the supplied curation labels the question open and says that the Alon--Rodl estimate applies only at a larger logarithmic threshold, while the proposed threshold with constant $C$ remains open. This is supplied dated curation, not independently verified literature assessment. The background expressly requests independent verification of time-sensitive status and cited claims.
• The record's statement status is corrected_verified; its supplied verification note says the official report was checked, the mathematical question isolated, and notation repaired for self-contained publication. These are provenance claims in the supplied record, not checks performed for this draft.