\chapter{Introduction}\label{sec:intro}

\section{Background}\label{sec:intro-background}

Let $n \ge 1$ and $q \ge 2$ be integers. We let $\log$ denote the natural logarithm, and let $\Pp$, $\E$, and $\Var$ denote probability, expectation, and variance, respectively. For every integer $k \ge 1$, we set $[k] = \{1, \dots, k\}$. We call a map $\sigma\colon[n] \to [q]$ a \emph{$q$-coloring} of a graph on $[n]$ if $\sigma(u) \ne \sigma(v)$ for all edges $\{u, v\}$. We call a graph \emph{$q$-colorable} if it has a $q$-coloring. We define its \emph{chromatic number} to be the least number of colors in such a coloring. For every integer $0 \le m \le \binom n2$, we let $G(n, m)$ denote a uniformly random simple graph on $[n]$ with $m$ edges. For $p \in [0, 1]$, we let $G(n, p)$ denote the random simple graph on $[n]$ in which each pair is an edge independently with probability $p$. This paper concerns $G(n, \lfloor cn\rfloor)$ and $G(n, d/n)$ for fixed constants $c, d \ge 0$ and sufficiently large $n$. The expected average degrees of these models tend to $2c$ and $d$, respectively.

The study of the chromatic number of sparse random graphs goes back to Erdős and Rényi, who asked in \cite[Section~10, p.~59]{erdos1960evolution} for the chromatic number of a random graph on $n$ vertices with about $cn$ edges, for $c > 1/2$. For every $q \ge 3$, Achlioptas and Friedgut proved that $q$-colorability has a sharp threshold \cite[Theorem~1.1]{achlioptas1999sharp}. More precisely, there exists a sequence $(\hat d_n)$ (which depends on $q$) such that for every fixed $\omega > 0$,
\begin{equation}\label{eq:intro-af}
\begin{gathered}
\lim_{n \to \infty} \Pp\bigl(G(n, \min\{1, \max\{0, (\hat d_n - \omega)/n\}\}) \text{ is $q$-colorable}\bigr) = 1, \\
\lim_{n \to \infty} \Pp\bigl(G(n, \min\{1, (\hat d_n + \omega)/n\}) \text{ is $q$-colorable}\bigr) = 0.
\end{gathered}
\end{equation}
Their proof rests on Friedgut's criterion for sharp thresholds \cite{friedgut1999sharp}, which relates a coarse threshold to the approximation of the property by the appearance of bounded subgraphs, and it leaves the dependence of $\hat d_n$ on $n$ undetermined. Achlioptas and Friedgut expressed the belief that $\hat d_n$ converges, and they recorded its convergence as an open problem \cite[Remark~1.2]{achlioptas1999sharp}. Achlioptas and Molloy had already noted that this convergence was widely conjectured \cite[p.~204]{achlioptas1997analysis}, and later works describe it as a well-known open problem \cite[Section~1.1]{cojaoghlan2016chromatica}, \cite[Section~1]{bapst2016condensation}. The goal of this paper is to prove that $\hat d_n$ converges for every $q \ge 3$.

We first recall the known bounds on the location of the transition. For $q = 3$, the random graph $G(n, d/n)$ is $3$-colorable with probability tending to one for $d \le 4.03$ \cite[Corollary~2]{achlioptas2003almost}, and with probability tending to zero for $d > 4.697$ \cite[Section~1.3]{ayre2022lower} (see \cite{chvatal1991almost,achlioptas1997analysis,kaporis2000note,dubois2002noncolourability} for earlier bounds). For general $q$, we set $\gamma_q = \log q / \log(q/(q - 1))$. We use $o_q(1)$ for a quantity tending to zero as $q \to \infty$, after the limit in $n$ at fixed $q$. A first-moment computation in $G(n, \lfloor cn \rfloor)$ gives non-colorability with probability tending to one when $c > \gamma_q$. Comparing the fixed-edge and binomial models gives the same conclusion for $G(n, d/n)$ when $d > 2\gamma_q$. We have $2\gamma_q = 2q \log q - \log q + o_q(1)$. Achlioptas and Naor showed that $G(n, d/n)$ is $q$-colorable with probability tending to one for $d < 2(q - 1) \log(q - 1)$, and that its chromatic number is concentrated on two explicit consecutive integers \cite[Theorem~1]{achlioptas2005two}. Coja-Oghlan and Vilenchik \cite[Theorem~1.1]{cojaoghlan2016chromatica} and Coja-Oghlan \cite[Theorem~1]{cojaoghlan2013upper} then proved that
\begin{equation}\label{eq:intro-largeq}
\liminf_{n \to \infty} \hat d_n \ge 2q \log q - \log q - 2 \log 2 - o_q(1), \qquad \limsup_{n \to \infty} \hat d_n \le 2q \log q - \log q - 1 + o_q(1),
\end{equation}
and Coja-Oghlan and Vilenchik also showed that the chromatic number of $G(n, d/n)$ is concentrated on a single value for all $d$ in an explicit set of asymptotic density one \cite[Theorem~1.2]{cojaoghlan2016chromatica}. These results locate the transition. However, they do not show that $\hat d_n$ converges.

Statistical physics gives precise, non-rigorous predictions. Statistical-physics computations place the $3$-colorability threshold near average degree $4.69$ \cite{mulet2002coloring}, refined numerically to $4.687(2)$ \cite[Table~II]{zdeborova2007phase}, and give the asymptotic form $2q \log q - \log q - 1 + o_q(1)$ for large $q$ \cite{krzakala2004threshold}, which agrees with the upper bound in \eqref{eq:intro-largeq}. The same theory predicts further transitions in the set of colorings below the colorability threshold \cite{krzakala2007gibbs,zdeborova2007phase}. Rigorous results on the number of colorings below that threshold were obtained for large $q$ \cite[Theorem~2.1]{bapst2016condensation} and later for all $q \ge 3$ \cite[arXiv:1611.00814v4, Theorem~1.2]{cojaoghlan2018information}.

For other random constraint satisfaction problems, the existence of a limiting threshold is known in several cases. The threshold of random $2$-SAT is at one clause per variable \cite{chvatal1992mick,goerdt1996threshold}, with a window of order $n^{2/3}$ clauses \cite[Theorem~1.1]{bollobas2001scaling}. The threshold of random $k$-XORSAT was determined for $k = 3$ in \cite{dubois2002xorsat} and for all $k \ge 3$ in \cite{pittel2016satisfiability}. Ding, Sly, and Sun proved the existence of the threshold for random $k$-SAT, and identified its value, for all sufficiently large $k$ \cite[Theorem~1]{ding2022proof}. For random $d$-regular graphs and all sufficiently large $q$, Coja-Oghlan, Efthymiou, and Hetterich located the $q$-colorability threshold in an interval of length less than one \cite[Theorem~1.1 and Corollary~1.2]{cojaoghlan2016chromaticb}. Since the degree is an integer, this leaves at most one degree at which the limiting behavior is not determined. This argument does not apply to $G(n, d/n)$, in which $d$ varies continuously.

Recently, two preprints claimed the existence of a limiting threshold for random $k$-SAT for every fixed $k \ge 3$, without identifying its value. These preprints use independent uniformly signed clauses, with distinct variables within each clause and with replacement between clauses. Carenini \cite[Theorem~1.1 and Corollary~1.2]{carenini2026polynomial} claims an upper bound of order $n^{1/2 + 1/k}$ clauses for the window, improving her earlier $O(n/\log n)$ bound \cite[Corollary~7.10]{carenini2026scaling}. She obtains the polynomial bound from a variance bound for the hitting time of unsatisfiability and deduces the existence of the threshold from a criterion of Abbe and Montanari \cite{abbe2014concentration}, in the form stated in \cite[Proposition~14]{perkins2025searching}. The preprint \cite[Theorem~1.1]{openai2026limiting} claims the same conclusion, combining a variance bound for a capped hitting time with an interpolation inequality and comparisons between systems of different sizes. The latter preprint explicitly credits Carenini with priority for the threshold-existence result \cite[abstract and Section~1]{openai2026limiting}. These preprints are unrefereed. We give self-contained proofs of the adaptations used here, while drawing on their arguments as described below. To the best of our knowledge, the convergence of $\hat d_n$ had not previously been established for a single value of $q \ge 3$.

\section{Main results}\label{sec:intro-results}

From now on, we fix an integer $q \ge 3$. Recall that
\begin{equation}\label{eq:intro-gamma}
\gamma_q = \frac{\log q}{\log(q/(q - 1))}.
\end{equation}
Our main result is the existence of the $q$-colorability threshold.

\begin{theorem}\label{thm:intro-main}
Let $q \ge 3$ be an integer. There exists $\alpha_q \in [1/2, \gamma_q]$ such that for every fixed real $c \ge 0$,
\[
\lim_{n \to \infty} \Pp\bigl(G(n, \lfloor cn \rfloor) \text{ is $q$-colorable}\bigr) =
\begin{cases}
1 & \text{if } 0 \le c < \alpha_q, \\
0 & \text{if } c > \alpha_q,
\end{cases}
\]
and for every fixed real $d \ge 0$,
\[
\lim_{n \to \infty} \Pp\bigl(G(n, d/n) \text{ is $q$-colorable}\bigr) =
\begin{cases}
1 & \text{if } 0 \le d < 2\alpha_q, \\
0 & \text{if } d > 2\alpha_q,
\end{cases}
\]
where $G(n, d/n)$ is defined for $n \ge d$.
\end{theorem}

We define $d_q = 2\alpha_q$ to be the threshold in terms of the asymptotic average degree. To relate our result to the sharp threshold sequence, we show that $\hat d_n \to d_q$. Fix $0 < \omega < d_q$. If $\hat d_n \ge d_q + \omega$ along a subsequence, the lower side of \eqref{eq:intro-af}, with shift $\omega/2$, and monotonicity imply that $G(n, (d_q + \omega/2)/n)$ is colorable with probability tending to one along that subsequence, contrary to \cref{thm:intro-main}. If $\hat d_n \le d_q - \omega$ along a subsequence, the upper side, with the same shift, implies that $G(n, (d_q - \omega/2)/n)$ is colorable with probability tending to zero, again a contradiction. This proves the claim.

The bounds on the limit inferior and limit superior in \eqref{eq:intro-largeq} now transfer directly to $d_q$. A bound at a fixed density transfers as well. If it failed for $d_q$, a density strictly between the two values would contradict monotonicity and \cref{thm:intro-main}. In particular, $4.03 \le d_3 \le 4.697$, and $d_q$ satisfies the two bounds in \eqref{eq:intro-largeq}.

The bounds $1/2 \le \alpha_q \le \gamma_q$ in \cref{thm:intro-main} are classical and are included for completeness. The upper bound is the first-moment bound mentioned above. The lower bound holds since, for $c < 1/2$, with probability tending to one every component of $G(n, \lfloor cn \rfloor)$ is a tree or has exactly one cycle \cite{erdos1960evolution}, \cite[Theorem~5.5, p.~112]{janson2000random}, and such graphs are $3$-colorable. \Cref{thm:intro-main} is an asymptotic statement. As we explain in \cref{rem:proof-finite}, our proof gives no further information on the value of $\alpha_q$ and no rate of convergence.

Our second result is a bound on the width of the transition in a random graph process. For a finite set $S$, we call a finite multiset of unordered pairs of distinct elements of $S$ a \emph{multigraph on $S$}, and we call its elements, counted with multiplicity, its \emph{occurrences}. We define a coloring of a multigraph on $S$ to be a map from $S$ to $[q]$ giving different colors to the endpoints of every occurrence. For $n \ge 2$, let $e_1, e_2, \dots$ be independent random pairs of distinct elements of $[n]$, each uniformly distributed on the $\binom{n}{2}$ pairs. We call the sequence $(e_i)_{i \ge 1}$ the \emph{edge process}. For each integer $m \ge 0$, we let $G_m$ denote its \emph{time-$m$ graph}, the multigraph on $[n]$ with occurrences $e_1, \dots, e_m$. Note that repeated pairs do not affect colorability. For $n \ge 2q$, we define $H$ to be the first integer $m \ge 0$ for which $G_m$ is not $q$-colorable. Thus
\[
H = \min\{m \ge 0 : G_m \text{ is not $q$-colorable}\}.
\]
By \cref{lem:pre-lifetime}, $H$ is finite almost surely.

\begin{theorem}\label{thm:intro-window}
Let $q \ge 3$ be an integer, let $\alpha_q$ be as in \cref{thm:intro-main}, and let $\epsilon \in (0, 1)$. There exist $C > 0$ and an integer $n_0 \ge 2q$, depending only on $q$ and $\epsilon$, and integers $m_n$ with $m_n/n \to \alpha_q$ as $n \to \infty$, such that
\begin{equation}\label{eq:intro-window}
\Pp\bigl(\abs{H - m_n} \le C n (\log n)^{-3/2}\bigr) \ge 1 - \epsilon \qquad \text{for all } n \ge n_0.
\end{equation}
\end{theorem}

Since $\Pp(H > m) = \Pp(G_m \text{ is $q$-colorable})$, \cref{thm:intro-window} implies that for all $n \ge n_0$ and integers $m \ge 0$,
\[
\begin{aligned}
\Pp(G_m \text{ is $q$-colorable}) &\ge 1 - \epsilon \qquad \text{if } m < m_n - C n (\log n)^{-3/2}, \\
\Pp(G_m \text{ is $q$-colorable}) &\le \epsilon \qquad \text{if } m \ge m_n + C n (\log n)^{-3/2}.
\end{aligned}
\]
Thus the probability that the process is colorable drops from $1 - \epsilon$ to $\epsilon$ within $O(n (\log n)^{-3/2})$ steps, and the window in the edge density $m/n$ has width $O((\log n)^{-3/2})$. We will compare this bound with known bounds on threshold widths in \cref{sec:intro-related}. We have not tried to optimize the exponent $3/2$. The convergence criterion in \cref{thm:red-convergence} requires the relative window widths to have a finite sum along exponentially growing sizes. The choice $(\log n)^{-3/2}$ meets this condition.

\Cref{thm:intro-main} is false for $q = 2$. We call a graph \emph{bipartite} if it admits a $2$-coloring. Pittel and Yeum showed that for every $d \in (0, 1)$,
\[
\lim_{n \to \infty} \Pp\bigl(G(n, d/n) \text{ is bipartite}\bigr) = e^{d/2} \Bigl(\frac{1 - d}{1 + d}\Bigr)^{1/4} \in (0, 1)
\]
\cite[Section~1, equation~(1.5)]{pittel2010frequently}. Hence there is no constant $d_2$ such that the probability of $2$-colorability tends to one below $d_2$ and to zero above it (see also the discussion in \cite[p.~64]{achlioptas1999sharp}). Our proof uses $q \ge 3$ in two places, which we describe in \cref{rem:proof-q3}. The essential one is the observation in \cref{lem:low-frozen} that, if a vertex receives the same color as another vertex in every coloring, then its neighbors use at least $q - 1 \ge 2$ colors in every coloring of the graph with this vertex removed.

Our proof has two parts, which we describe in more detail in \cref{sec:overview}. We begin by showing that the existence of $\alpha_q$ follows from the summable window bound just described, at every sufficiently small fixed probability level. To do so, we compare the probabilities of colorability at different numbers of vertices through an interpolation inequality of Bayati, Gamarnik, and Tetali \cite[Theorem~5 and Proposition~2]{bayati2013combinatorial}. We then prove the window bound of \cref{thm:intro-window}. We define the \emph{expected lifetime} of a colorable graph to be the expected number of independent uniformly random pair additions needed to make it non-colorable, including the addition that destroys colorability. A variance argument reduces the window bound to controlling this lifetime for $G_{H - 1}$.

We call $e_H$ the \emph{final edge}. For a colorable graph, we call two distinct vertices a \emph{frozen pair} if they receive the same color in every coloring, and we call each equivalence class under equality in every coloring a \emph{frozen class}. The final edge joins a frozen pair of $G_{H - 1}$. We count degrees with multiplicity. We treat separately the final edges with an endpoint of low degree (at most $\lfloor(\log n)^{1/4}\rfloor$), by identifying random vertices, and the final edges between vertices of high degree, by deleting occurrences and controlling the growth of the logarithm of the size of a frozen class.

\section{Related work}\label{sec:intro-related}

We now discuss the sources of the methods that we use, and the known bounds on the width of the transition.

The comparison of different system sizes in \cref{app:conv} uses the interpolation method. System-splitting interpolation was used by Guerra and Toninelli to prove the existence of the limiting free energy of the Sherrington--Kirkpatrick model, by interpolating between a large system and two independent subsystems \cite[Section~3]{guerra2002thermodynamic}. Franz and Leone \cite{franz2003replicaa} and Panchenko and Talagrand \cite{panchenko2004bounds} developed free-energy bounds for diluted models with Poisson numbers of interactions, including random $k$-SAT, under their respective interaction and arity hypotheses. Bayati, Gamarnik, and Tetali gave a combinatorial version for sparse random graphs \cite{bayati2013combinatorial}. They proved the convergence of the normalized optimal values of several problems and of the normalized logarithm of the probability of $q$-colorability \cite[Theorem~1]{bayati2013combinatorial}. However, such a limit does not by itself locate a transition from probability one to probability zero, since it is consistent with probabilities that tend to zero more slowly than exponentially. For coloring, they also compared the probability that a graph is colorable with the probability that two smaller disjoint graphs are colorable \cite[Theorem~5 and Proposition~2]{bayati2013combinatorial}, and their proof of this comparison uses the classes of vertices that receive the same color in every coloring. Our product inequality, \cref{lem:conv-interp}, is its form for a Poisson number of edges.

To pass from comparisons of system sizes to convergence, one uses a principle of near-superadditivity. De Bruijn and Erdős proved such a principle for sequences that are subadditive up to an error satisfying an integrability condition, for comparable sizes \cite[Theorem~23]{debruijn1952some}, and Abbe and Montanari gave a version with summable errors \cite[arXiv:1006.3786v1, Section~4.3, Lemma~8 and Remark~3]{abbe2014concentration}. In \cite[Section~5]{openai2026limiting}, the product inequality \cite[Lemma~5.2]{openai2026limiting} is used to compare the normalized center of the transition for the combined system with the minimum of the centers for the two parts, with polynomially small errors, and a balanced tree of blocks yields convergence \cite[Lemma~5.4]{openai2026limiting}. \Cref{app:conv} adapts this argument to quantiles of the hitting time and to errors that are only summable along $n = \lfloor e^k \rfloor$. We show in \cref{rem:conv-necessity} that a window of order $n/\log n$ would not suffice for this argument.

The reduction of the window to the expected lifetime of the last colorable graph, in \cref{sec:red-deletion}, has several antecedents. Aldous \cite[Theorem~1(b)]{aldous1991threshold} considered the cover time of a finite set by independent copies of a random subset, the first time at which their union is the whole set. He bounded the variance of the cover time by an absolute constant times its mean times the expected time that a fresh sequence of such subsets needs to cover the set left uncovered just before the cover time. Coloring fits this framework, if each pair $\{u, v\}$ covers the maps $\sigma \colon [n] \to [q]$ with $\sigma(u) = \sigma(v)$. In this case, $H$ is the cover time, and the set left uncovered at time $H - 1$ is the set of colorings of $G_{H - 1}$. Carenini applied Aldous's bound to the last satisfiable formula in random $k$-SAT \cite[Theorem~4.1]{carenini2026polynomial}. In \cite[Lemmas~3.1 and~3.2]{openai2026limiting}, the variance of a capped hitting time is bounded through the Efron--Stein inequality \cite{efron1981jackknife,steele1986efron}, in the form \cite[(3.6)]{boucheron2005moment} in which one variable is omitted, by deleting one clause at a time without renumbering the other clauses, and a later preprint combines expected lifetimes with such deletions \cite[Section~3.3, Lemma~3.4]{openai2026variance}. \Cref{lem:red-deletion} follows the deletion argument of \cite{openai2026limiting} and evaluates the sum of the squared deletion delays exactly, in terms of the expected lifetime of the last colorable graph.

The estimates specific to $k$-SAT in \cite{carenini2026polynomial,openai2026limiting} bound the sum over time of the fraction of variables that take the same value in every satisfying assignment \cite[Proposition~3.2]{carenini2026polynomial}, \cite[Proposition~2.2]{openai2026limiting}. These proofs delete a variable and compare the clauses that contained it, which become clauses of length $k - 1$, with clauses of length $k$. This step does not carry over to colorings. Since permuting the colors maps colorings to colorings, no vertex of a colorable graph receives a fixed named color in every coloring. What can be forced is the equality of two colors. Recall that the final edge $e_H$ joins two vertices $u$ and $v$ such that $\sigma(u) = \sigma(v)$ for every coloring $\sigma$ of $G_{H - 1}$.

Culberson and Gent studied frozen pairs and their development as edges are added to a graph, and used frozen-pair counts to compute conditional one-edge survival probabilities in a process without replacement \cite[Sections~2.1 and~3.3]{culberson2001frozen}. The hazard identity in \cref{lem:pre-hazard} is the version for independent pairs sampled with replacement. For a satisfiable Boolean formula, we call the literals true in every satisfying assignment its \emph{backbone} \cite{monasson1996entropy,monasson1999determining}. Following \cite{bollobas2001scaling}, we call the literals whose addition makes some satisfiable subformula unsatisfiable its \emph{spine}. These notions record an absolute Boolean value, whereas a frozen pair records equality without specifying a named color. In \cite[Section~3.3]{bollobas2001scaling}, the probability that the next clause makes a $2$-SAT formula unsatisfiable is expressed through the spine, and \cref{lem:pre-hazard} is the analogous identity for frozen pairs. Other notions of freezing concern a variable that has one value throughout a specified restricted family of solutions \cite{achlioptas2009random,molloy2018freezing,semerjian2008freezing}. Frozen pairs here quantify over all colorings. Our estimates for the frozen pairs of the last colorable graph, in \cref{sec:low,sec:high}, replace the estimates specific to $k$-SAT. We now describe the ingredients of these estimates.

To treat final edges with an endpoint of low degree, we identify vertices. Let $Z$ be a nonempty set of vertices of a graph. Its colorings that are constant on $Z$ correspond to the colorings of the graph in which $Z$ is identified to a single vertex. For two nonadjacent vertices, this correspondence underlies the addition--identification relation for chromatic polynomials \cite[Section~3, Theorem~1]{read1968introduction}. We combine it with the splitting of a Poisson process of edges at a vertex \cite[Theorems~5.2, 5.6, and~5.8, Corollary~5.9]{last2018lectures}, and we prove in \cref{prop:low-identify} that identifying at most $(\log n)^{1/4}$ random vertices advances the hitting time of non-colorability, in expectation, by $O(n^{3/8})$.

For final edges between vertices of high degree, we instead delete edge occurrences. The deletion identities are the analogue, for a fixed number of independent points, of the Mecke equation for Poisson processes \cite{mecke1967stationare}, \cite[Theorem~4.1]{last2018lectures}. We call an occurrence at one endpoint of a frozen pair \emph{pivotal} for that pair if deleting it removes the forced equality; otherwise we call it \emph{non-pivotal}. This is the usual notion of sensitivity to one coordinate \cite{russo1982approximate}, applied to the event that adding the given pair destroys colorability. The main estimate of \cref{sec:high} bounds the total, along the process, of the density of a relation that describes how the frozen class of a vertex grows when an edge at this vertex is added. We prove it by charging this density to the growth of the logarithm of the size of the frozen class. Bounds on hitting and occupation times through a function whose expected increments can be controlled are classical \cite[Sections~2--3]{hajek1982hitting}. In the $k$-SAT preprints, Carenini bounds the occupation of states through a concave function of their expected lifetime \cite[Lemma~3.1]{carenini2026polynomial}, and a later preprint charges the visits of the process above a level of the probability of becoming unsatisfiable to the expected lifetime at the first visit \cite[Section~4.1, Lemma~4.1]{openai2026variance}. A related bounded-potential occupation argument appears in \cite[Lemmas~2.2 and~4.1]{openai2026linear}: expected increments of a bounded monotone potential control accumulated powers of short-clause killing probabilities. The inequality that we need between the density of the relation and the expected growth of the frozen class, \cref{lem:high-onestep}, is specific to colorings.

Finally, we compare \cref{thm:intro-window} with known bounds on the width of transitions. At fixed probability levels, for every nontrivial increasing graph property that is invariant under relabeling, Friedgut and Kalai proved that the transition in $G(n, p)$ takes place within an interval of values of $p$ of length $O(1/\log n)$ \cite[Theorem~1.1, p.~2993]{friedgut1996every}, and Bourgain and Kalai improved this to $O((\log n)^{-2 + \delta})$ for every $\delta > 0$ \cite{bourgain1997influences}, \cite[Theorem~1]{bourgain1999threshold}. A recent unrefereed preprint claims the bound $O((\log n)^{-2})$ for every nontrivial monotone graph property invariant under relabeling \cite[Theorem~1.1]{openai2026graphthreshold}. These additive bounds do not give a shrinking relative window when $p$ is of order $1/n$; the derivative formulation of the Bourgain--Kalai improvement also restricts how close $p$ may be to zero or one. The small-$p$ refinement in \cite[Corollary~3.3, p.~2996]{friedgut1996every} gives an upper bound $O(1/n)$ when $p = \Theta(1/n)$, corresponding to $O(n)$ expected edges; it still does not yield a shrinking relative window. The theorem of Achlioptas and Friedgut shows that the window of $q$-colorability has width $o(n)$ in the number of edges, with no rate, and \cref{thm:intro-window} improves this to $O(n (\log n)^{-3/2})$. In the other direction, Wilson proved that this window has width at least of order $\sqrt{n}$ edges for every $q \ge 3$ \cite[Corollary~6]{wilson2002critical}.

We do not know the true order of the window. For comparison, the window of random $2$-SAT has order $n^{2/3}$ clauses \cite[Theorem~1.1]{bollobas2001scaling}. For random $k$-SAT, Carenini claims a window upper bound of order $n^{1/2 + 1/k}$ clauses \cite[Theorem~1.1]{carenini2026polynomial}, and two further preprints claim that the hitting time of unsatisfiability has variance of order $n$, for $k \ge 4$ \cite[Theorem~1.1]{openai2026variance} and for $k = 3$ \cite[Theorem~1.1]{openai2026linear}. As we explain in \cref{rem:proof-sqrt}, when the probability that $H$ lies strictly above the lower quantile and at or below the upper quantile stays bounded away from zero, the variance bound of \cref{sec:red} cannot certify a window smaller than order $\sqrt n$.

\section{Organization}\label{sec:intro-organization}

\Cref{sec:overview} gives an overview of the proof. \Cref{sec:pre} collects definitions and elementary facts on the edge process, frozen pairs, and expected lifetimes. \Cref{sec:red} states the convergence criterion and reduces the window bound to two estimates for the final edge, one for endpoints of low degree and one for endpoints of high degree. \Cref{sec:low} proves the first estimate. This is the main place where the assumption $q \ge 3$ is used. \Cref{sec:high} proves the second estimate, which holds for $q = 2$ as well. \Cref{sec:proof} combines these results and proves \cref{thm:intro-main,thm:intro-window}. \Cref{app:conv} proves the convergence criterion.