==== TABLE OF CONTENTS ====
A-Sharp-Threshold-Bound-for-Monotone-Graph-Properties//block.tex
A-Sharp-Threshold-Bound-for-Monotone-Graph-Properties//fourier.tex
A-Sharp-Threshold-Bound-for-Monotone-Graph-Properties//graph.tex
A-Sharp-Threshold-Bound-for-Monotone-Graph-Properties//introduction.tex
A-Sharp-Threshold-Bound-for-Monotone-Graph-Properties//main.tex
A-Sharp-Threshold-Bound-for-Monotone-Graph-Properties//references.tex
A-Sharp-Threshold-Bound-for-Monotone-Graph-Properties//threshold.tex
===========================
==== BEGIN A-Sharp-Threshold-Bound-for-Monotone-Graph-Properties//block.tex ====
\begin{figure}[tb]
\centering
\setlength{\unitlength}{0.93pt}
\begin{picture}(460,190)
\put(12,176){\makebox(202,12){\small (a) The free coordinate set $F_B$}}
\put(246,176){\makebox(202,12){\small (b) One Fourier support $S$}}
\linethickness{0.45pt}
\put(40,164){\line(1,0){52}}
\qbezier(92,164)(108,164)(108,148)
\put(108,56){\line(0,1){92}}
\qbezier(108,56)(108,40)(92,40)
\put(40,40){\line(1,0){52}}
\qbezier(40,40)(24,40)(24,56)
\put(24,56){\line(0,1){92}}
\qbezier(24,148)(24,164)(40,164)
\put(274,164){\line(1,0){52}}
\qbezier(326,164)(342,164)(342,148)
\put(342,56){\line(0,1){92}}
\qbezier(342,56)(342,40)(326,40)
\put(274,40){\line(1,0){52}}
\qbezier(274,40)(258,40)(258,56)
\put(258,56){\line(0,1){92}}
\qbezier(258,148)(258,164)(274,164)
\put(23,151){\makebox(15,10){$B$}}
\put(257,151){\makebox(15,10){$B$}}
\thinlines
\qbezier(47,133)(65.5,117)(84,101)
\qbezier(84,101)(65.5,85)(47,69)
\put(47,69){\line(0,1){64}}
\qbezier(47,133)(110.5,142)(174,151)
\qbezier(47,133)(121,125)(195,117)
\qbezier(47,133)(121,103.5)(195,74)
\qbezier(47,133)(110.5,86.5)(174,40)
\qbezier(84,101)(129,126)(174,151)
\qbezier(84,101)(139.5,109)(195,117)
\qbezier(84,101)(139.5,87.5)(195,74)
\qbezier(84,101)(129,70.5)(174,40)
\qbezier(47,69)(110.5,110)(174,151)
\qbezier(47,69)(121,93)(195,117)
\qbezier(47,69)(121,71.5)(195,74)
\qbezier(47,69)(110.5,54.5)(174,40)
\put(47,133){\circle*{5}}
\put(84,101){\circle*{5}}
\put(47,69){\circle*{5}}
\put(174,151){\circle*{5}}
\put(195,117){\circle*{5}}
\put(195,74){\circle*{5}}
\put(174,40){\circle*{5}}
\put(24,9){\makebox(190,22){\shortstack{\scriptsize All displayed edges are free.\\[-1pt]
\scriptsize Edges wholly outside $B$ are fixed.}}}
\linethickness{1pt}
\qbezier(318,101)(363,126)(408,151)
\qbezier(318,101)(373.5,109)(429,117)
\qbezier(408,151)(418.5,134)(429,117)
\put(281,133){\circle{5}}
\put(318,101){\circle*{6}}
\put(281,69){\circle{5}}
\put(408,151){\circle*{6}}
\put(429,117){\circle*{6}}
\put(429,74){\circle{5}}
\put(408,40){\circle{5}}
\put(302,88){\makebox(13,12){$u$}}
\put(410,156){\makebox(19,10){\scriptsize $v_1$}}
\put(435,115){\makebox(19,10){\scriptsize $v_2$}}
\put(435,72){\makebox(19,10){\scriptsize $v_3$}}
\put(410,26){\makebox(19,10){\scriptsize $v_4$}}
\put(327,143){\makebox(63,10){\scriptsize survives}}
\put(430,146){\makebox(28,20){\shortstack{\scriptsize fixed\\[-1pt]\scriptsize by $y$}}}
\thinlines
\put(440,142){\vector(-1,-1){16}}
\put(257,9){\makebox(190,15){\small $|S\cap F_B|=d_S(u)=2$}}
\end{picture}
\caption{The block restriction and the one-vertex event.
In (a), $F_B$ contains every edge incident with $B$, including its
internal edges; only edges with both endpoints outside $B$ are fixed.
In (b), only support edges are drawn, and filled vertices are the
nonisolated vertices $V(S)$. The event $B\cap V(S)=\{u\}$ leaves
both support edges incident with $u$ free. The exterior support
edge is fixed, and its contribution is retained by the exact
averaging identity \eqref{eq:restriction-mass}.}
\label{fig:block}
\end{figure}
==== END A-Sharp-Threshold-Bound-for-Monotone-Graph-Properties//block.tex ====
==== BEGIN A-Sharp-Threshold-Bound-for-Monotone-Graph-Properties//fourier.tex ====
\section{A low-degree estimate on biased products}\label{sec:fourier}
We bound the mass of low-degree Fourier coefficients for Boolean
functions whose individual influences are small compared with their
total influence. The bound is linear in total influence, so it can be
averaged over the conditioned coordinates in Section~\ref{sec:graph}.
Let $J$ be a finite coordinate set, let $00$. Hence
$\sigma\log(4/\sigma)\le\tfrac12\log8<2$, and
\[
\rho^{-2k}
=m^{\sigma\log(4/\sigma)/32}\le m^{1/16}.
\]
If $I(h)\le m^{1/4}$, the hypothesis implies
\[
\sum_i I_i(h)^{3/2}
\le\sqrt{\frac{I(h)}m}\,I(h)
\le m^{-3/8}I(h).
\]
The preceding estimates bound the desired sum by
$\sigma^2m^{-5/16}I(h)\le m^{-1/4}I(h)$, including when $I(h)=0$.
If $I(h)>m^{1/4}$, Parseval and Booleanity instead give
\[
\sum_{1\le |S|\le k}\widehat h(S)^2
\le\E h^2\le10$,
\begin{align}
\E_y\sum_{\substack{A\subseteq F\\1\le |A|\le k}}
\widehat{f_y}(A)^2
&=\sum_{\substack{S\subseteq E_n\\1\le|S\cap F|\le k}}
\widehat f(S)^2,
\label{eq:restriction-mass}\\
\E_y I(f_y)&=\sum_{e\in F}I_e(f).
\label{eq:restriction-influence}
\end{align}
\end{lemma}
\begin{proof}
Expand $f$ in the product Fourier basis and integrate over $x$.
For each $A\subseteq F$ this gives the exact finite identity
\[
\widehat{f_y}(A)
=\sum_{D\subseteq H}\widehat f(A\cup D)\chi_D(y).
\]
Orthonormality on the exterior coordinates therefore gives
$\E_y\widehat{f_y}(A)^2
=\sum_{D\subseteq H}\widehat f(A\cup D)^2$.
Summing over $A$ proves \eqref{eq:restriction-mass}. In particular,
there is no constraint on the exterior Fourier degree $|D|$.
For $e\in F$, the pivotal event for $f_y$ at $e$ is the pivotal event
for $f$ at $e$ with the exterior coordinates fixed to $y$. Averaging
over $y$ and the remaining free coordinates gives
$\E_y I_e(f_y)=I_e(f)$; summation proves
\eqref{eq:restriction-influence}.
\end{proof}
\begin{proposition}[The block estimate]
\label{prop:block}
Let $3\le m\le n$ be an integer, let $B$ be uniform among the
$m$-element subsets of $[n]$, and set
\[
F_B=\{e\in E_n:e\cap B\ne\varnothing\},
\qquad k=\frac{\sigma\log m}{64}.
\]
Then
\begin{equation}
\sum_{S\subseteq E_n}
\Pr_B\{1\le |S\cap F_B|\le k\}\widehat f(S)^2
\le \frac{2m}{n}\,m^{-1/4}I(f).
\label{eq:block-average}
\end{equation}
\end{proposition}
\begin{proof}
Fix $B$, and fix an arbitrary assignment $y$ to
$H_B=E_n\setminus F_B$. The free set $F_B$ contains \emph{all} edges
with at least one endpoint in $B$: both edges within $B$ and edges
from $B$ to its complement. Every permutation supported on $B$
fixes each edge of $H_B$ individually, and hence fixes $y$.
The restricted function $f_y$ is consequently invariant under this
permutation group even if the graph encoded by $y$ has no symmetry.
The free-edge orbits are precisely the $\binom m2$ edges within $B$
and, for each \emph{fixed} $w\in[n]\setminus B$, the $m$ edges
$\{\{u,w\}:u\in B\}$. Every orbit has size at least $m$, since
$m\ge3$. The product law and the pivotal events are preserved by
these permutations, so influences agree within each orbit.
It follows that
\[
I_e(f_y)\le\frac{I(f_y)}m\qquad(e\in F_B).
\]
Lemma~\ref{lem:low-degree} applies separately to every $y$. Its
right-hand side is linear in $I(f_y)$, so averaging and using
Lemma~\ref{lem:restriction} gives
\[
\sum_{\substack{S\subseteq E_n\\1\le |S\cap F_B|\le k}}
\widehat f(S)^2
\le m^{-1/4}\sum_{e\in F_B}I_e(f).
\]
Finally average over $B$. Each endpoint of a fixed edge belongs to
$B$ with probability $m/n$, whence
$\Pr_B(e\in F_B)\le2m/n$. This proves
\eqref{eq:block-average}.
\end{proof}
\begin{lemma}[Capturing low Fourier levels]
\label{lem:block-capture}
Suppose $t=\log n\ge16$, and put
\[
m=\lfloor\sqrt n\rfloor,
\qquad k=\frac{\sigma\log m}{64}.
\]
Then
\begin{equation}
\sum_{\substack{S\subseteq E_n\\1\le |S|\le k^2/2}}
\widehat f(S)^2
\le 4m^{-1/4}I(f).
\label{eq:captured-mass}
\end{equation}
\end{lemma}
\begin{proof}
Fix a nonempty $S\subseteq E_n$ with $s=|S|\le k^2/2$, viewed as
the edge set of a simple graph. Let $V(S)$ be its set of nonisolated
vertices and write $v=|V(S)|$. Since $s\le\binom v20$.
For the remaining Fourier degrees, the Dirichlet identity
\eqref{eq:dirichlet} gives
\begin{equation}
\sum_{|S|>k^2/2}\widehat f(S)^2
\le\frac2{k^2}\sum_S|S|\widehat f(S)^2
=\frac{2\sigma^2}{k^2}I(f).
\label{eq:graph-tail}
\end{equation}
This remains valid for $k^2/2<1$, when the left side includes all
nonconstant coefficients. Combining \eqref{eq:parseval},
\eqref{eq:captured-mass}, and \eqref{eq:graph-tail} yields
\begin{equation}
\Var(f)\le
\left(4m^{-1/4}+\frac{2\sigma^2}{k^2}\right)I(f).
\label{eq:graph-variance-preconstant}
\end{equation}
For completeness, all constants can be bounded independently of
$p$ and $n$. Since $m\ge\sqrt n/2$ and $t\ge16$,
$\log m\ge t/2-\log2\ge t/3$. Thus
\[
\frac{2\sigma^2}{k^2}
=\frac{8192}{(\log m)^2}\le\frac{73728}{t^2}.
\]
The cancellation of $\sigma^2$ is exact, even when $p$ is arbitrarily
close to $0$ or $1$. Also, $t^2e^{-t/8}$ is nonincreasing for
$t\ge16$, so
\[
4m^{-1/4}t^2
\le4\,2^{1/4}t^2e^{-t/8}
\le4\,2^{1/4}\,256e^{-2}<256.
\]
Thus the right-hand side of \eqref{eq:graph-variance-preconstant} is at most
$(73728+256)I(f)/t^2$, which is at most
$2^{17}I(f)/t^2$.
If instead $2\le n0$ and $0<\varepsilon<1/2$, their graph-property
bound is
\[
p_{1-\varepsilon}(\mathcal P)-p_\varepsilon(\mathcal P)
\le C_{\eta,\varepsilon}(\log n)^{-2+\eta}.
\]
Thus their result approached the conjectured exponent arbitrarily
closely. Further progress through Fourier estimates is described below;
Friedgut gives a broader account of the influence method
in~\cite{Friedgut22}.
Two companion papers address complementary threshold-location
questions: comparison of integral and fractional covers of increasing
families~\cite[Theorem~1.1]{ExpectationEquivalence2026}, and comparison
of graph-containment thresholds with expected subgraph
counts~\cite[Theorem~1.1]{SecondKahnKalai2026}.
The present theorem controls the width of a transition for arbitrary
increasing graph properties. Its proof does not use either comparison.
Here is the stronger estimate that drives the proof. For a Boolean function $f:\{0,1\}^{E_n}\to\{0,1\}$, define its \emph{pivotal influence} at edge $e$ and its \emph{total influence} as follows. Here $x_{e\leftarrow b}$ denotes $x$ with coordinate $e$ set to $b\in\{0,1\}$, and the probability is over all coordinates other than $e$.
\[
I_{e,p}(f)=\Pr_p\bigl(f(x_{e\leftarrow1})\ne f(x_{e\leftarrow0})\bigr),
\qquad I_p(f)=\sum_{e\in E_n}I_{e,p}(f).
\]
\begin{theorem}[Variance and influence]
\label{thm:variance}
For every integer $n\ge2$, every Boolean function $f$ on $E_n$ invariant under vertex permutations, and every $00$
\cite[arXiv version~2, Section~7.4]{KKLMS20}.
This is an influence estimate at $p=1/2$; a threshold-width bound
requires control throughout the transition interval.
Theorem~\ref{thm:variance} removes the iterated-logarithm loss and
holds uniformly for every $00$ throughout $(0,1)$. Thus, by continuity, every quantile $p_a$ is the unique interior point satisfying $\mu(p_a)=a$.
On the interval $[p_\varepsilon,p_{1-\varepsilon}]$, division in \eqref{eq:differential} is legitimate and gives
\[
\frac{d}{dp}\log\frac{\mu(p)}{1-\mu(p)}
=\frac{\mu'(p)}{\mu(p)(1-\mu(p))}
\ge\frac{(\log n)^2}{C_0}.
\]
Integration yields
\[
p_{1-\varepsilon}-p_\varepsilon
\le\frac{2C_0}{(\log n)^2}
\log\frac{1-\varepsilon}{\varepsilon}.
\]
Finally, $4\varepsilon(1-\varepsilon)\le1$ implies
\[
\log\frac{1-\varepsilon}{\varepsilon}
\le 2\log\frac1{2\varepsilon}.
\]
This proves \eqref{eq:threshold} with $4C_0=2^{19}$ for the entire range $0<\varepsilon<1/2$.
\end{proof}
To recover the additive formulation of \cite[Conjecture~1.2]{FK96}, set
\[
\delta=\frac{2^{19}}{(\log n)^2}\log\frac1{2\varepsilon},
\]
and suppose $\mu(p)>\varepsilon$. Then $p>p_\varepsilon$, so
Theorem~\ref{thm:threshold} gives $p+\delta>p_{1-\varepsilon}$.
Hence $\mu(p+\delta)>1-\varepsilon$ whenever $p+\delta\le1$;
for larger increments, the endpoint $1$ already has probability one.
Conversely, when $p_\varepsilon+\delta<1$, apply this strict formulation
at $p>p_\varepsilon$ and let $p\downarrow p_\varepsilon$.
Continuity gives $\mu(p_\varepsilon+\delta)\ge1-\varepsilon$, which
is the quantile bound. When $p_\varepsilon+\delta\ge1$, that bound
is automatic.
The same log-odds estimate describes the transition around its median
$p_*=p_{1/2}$. The log odds vanish at $p_*$, so integration from the
median gives, with $C_0=2^{17}$,
\[
\begin{aligned}
\mu(p_*-s)
&\le \frac{1}{1+\exp\!\bigl(s(\log n)^2/C_0\bigr)}
&&(0\le s\le p_*),\\
1-\mu(p_*+s)
&\le \frac{1}{1+\exp\!\bigl(s(\log n)^2/C_0\bigr)}
&&(0\le s\le1-p_*).
\end{aligned}
\]
The endpoint cases follow by continuity.
==== END A-Sharp-Threshold-Bound-for-Monotone-Graph-Properties//threshold.tex ====