Sharp Triangle Threshold in Pseudorandom Graphs

Definitions and mathematical statement

The supplied record contains two incompatible mathematical targets. The cleaned statement concerns a spectral threshold for triangles, whereas the original extraction concerns a random triangle removal process. Consequently, the following threshold formulation is conditional on the cleaned statement being the intended target; its equivalence to the original source has not been established here.

For this conditional formulation, use the following conventional meaning of an $(n,d,\lambda)$-graph: a finite simple undirected $d$-regular graph $G$ on $n\geq 3$ vertices, where $0\leq d\leq n-1$, $\lambda\geq 0$, and every eigenvalue of the adjacency matrix restricted to the subspace orthogonal to the all-ones vector has absolute value at most $\lambda$. This spectral convention and graph category are not explicitly defined in the supplied record and require source confirmation. A triangle is a set of three vertices inducing all three possible edges; a graph is triangle-free if it contains no triangle.

The cleaned question asks whether there exists a real constant $c_0$ such that both of the following hold:

1. For every $\varepsilon>0$, there exists an integer $N_{\varepsilon}$ such that, for every integer $n\geq N_{\varepsilon}$ and every $(n,d,\lambda)$-graph $G$, \[ \lambda<(c_0-\varepsilon)\frac{d^2}{n} \quad\Longrightarrow\quad G\text{ contains a triangle}. \]
2. For every $\varepsilon>0$ and every integer $N\geq 3$, there exist an integer $n\geq N$, parameters $d,\lambda$, and a triangle-free $(n,d,\lambda)$-graph $G$ such that \[ \lambda<(c_0+\varepsilon)\frac{d^2}{n}. \]

No additional growth restriction on $d$ or $\lambda$ is supplied. The record does not explicitly specify the range of $c_0$.

The cleaned statement further asks whether the first inequality forces "many triangles" or a "proportionally large triangle factor." These phrases do not specify mathematical conclusions. If $t(G)$ denotes the number of triangles and $\nu_3(G)$ the maximum number of pairwise vertex-disjoint triangles, then possible quantitative targets would involve lower bounds on $t(G)$ or $\nu_3(G)$, but the required bounds and their parameter dependence are absent. A triangle factor in its usual sense is a collection of vertex-disjoint triangles covering every vertex and requires $3\mid n$; a large partial collection is a triangle packing. The supplied wording does not determine which is intended.

For comparison, the original extraction, following an incomplete fragment about $c_0$, attributes a different Problem 6 to Mehtaab Sawhney. It asks about a random triangle removal process in $K_n$ run for $n^2/6-n^{1.99}$ steps, with output triangle set $\mathcal T_n$: do there exist a constant $C>0$ and events $E_n$ with $\Pr(E_n)=1-o(1)$ as $n\to\infty$ such that, for every $k\geq 1$ and every choice of $k$ distinct triangles $T_1,\ldots,T_k$ of $K_n$, \[ \Pr\left(\{T_1,\ldots,T_k\}\subseteq\mathcal T_n\mid E_n\right) \leq \left(\frac{C}{n}\right)^k? \] Here $C$ is uniform in $n$, $k$, and the chosen triangles, and the events $E_n$ must work simultaneously for these choices. The extraction explicitly allows $k$ to grow with $n$, mentioning $k=n^2/12$ as an example, and remarks that the estimate restricted to $k\leq n^{1/10}$ is relatively straightforward. The process law, integer rounding of the number of steps, handling of early termination, and precise meaning of the output set are not supplied. This alternative question is retained as conflicting source evidence, not asserted to be equivalent to the spectral threshold question.

Short English statement

Conditionally interpreting the cleaned statement, the question asks for a common sharp spectral constant separating guaranteed triangles from arbitrarily large triangle-free regular graphs, together with unspecified stronger triangle-counting or packing conclusions. The original extraction instead asks for a uniform conditional probability bound for triangles selected by a random removal process. The intended target and the quantitative strengthening require source review.

Sources

• Supplied local UnsolvedMath registry record, permanent ID 30005115, title Sharp Triangle Threshold in Pseudorandom Graphs, source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. The record gives proposed year 2022 and no proposer for the cleaned threshold question.
• Supplied report citation: Combinatorics, Probability and Computing (2023), Oberwolfach Reports, DOI 10.4171/owr/2022/22, pp. 1165--1237. Supplied source link: https://doi.org/10.4171/owr/2022/22. The background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions.
• Supplied literature source, labelled "official OWR report": https://publications.mfo.de/bitstream/handle/mfo/3964/OWR_2022_22.pdf?isAllowed=y&sequence=4.
• Literature assessment dated exactly 2026-08-22: the supplied curation labels the threshold problem partially solved and states that the triangle-existence and triangle-free sides are known with different constants, while identifying a common sharp constant remains open. This is supplied dated curation, not an independently verified assessment; the background explicitly requests independent verification of time-sensitive status and cited claims.
• The registry labels the cleaned statement corrected_verified and reports that the official report was checked directly. These are supplied verification claims, not verification performed for this draft. The conflicting original extraction names Mehtaab Sawhney and Problem 6 in connection with the random triangle removal question; that attribution is not transferred to the threshold question.