64c3814
==== 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 $0<p<1$, and put
$\sigma=\sqrt{p(1-p)}$. Expectations and norms in this section are with
respect to the product Bernoulli-$p$ measure on the indicated coordinates;
in particular, $\|g\|_q=(\E|g|^q)^{1/q}$. Define
\[
\chi_i(x)=\frac{x_i-p}{\sigma},\qquad
\chi_S(x)=\prod_{i\in S}\chi_i(x),\qquad \chi_\varnothing=1.
\]
Each $\chi_i$ has mean zero and second moment one. Independence therefore
makes the $2^{|J|}$ functions $\chi_S$, $S\subseteq J$, orthonormal.
They form a basis of the $2^{|J|}$-dimensional space of real functions on
$\{0,1\}^J$. Thus, with $\widehat g(S)=\E[g\chi_S]$,
\begin{equation}\label{eq:parseval}
g=\sum_{S\subseteq J}\widehat g(S)\chi_S,\qquad
\E g^2=\sum_{S\subseteq J}\widehat g(S)^2,\qquad
\Var(g)=\sum_{\varnothing\ne S\subseteq J}\widehat g(S)^2.
\end{equation}
For $i\in J$, write
$\Delta_i g(x)=g(x_{J\setminus\{i\}},1)-g(x_{J\setminus\{i\}},0)$,
a function on the remaining coordinates. Integrating just coordinate $i$
gives
\[
\E_i[g\chi_i]
=\frac{p(1-p)}{\sigma}
\bigl(g(x_{J\setminus\{i\}},1)-g(x_{J\setminus\{i\}},0)\bigr)
=\sigma\Delta_i g.
\]
Consequently, for $A\subseteq J\setminus\{i\}$,
$\widehat g(A\cup\{i\})=\sigma\widehat{\Delta_i g}(A)$,
where the latter Fourier coefficient is taken on $J\setminus\{i\}$.
For Boolean $h:\{0,1\}^J\to\{0,1\}$, set
\[
I_i(h)=\Pr(\Delta_i h\ne0),\qquad I(h)=\sum_{i\in J}I_i(h).
\]
Since $\Delta_i h\in\{-1,0,1\}$, Parseval on the remaining coordinates
and then summation over $i$ give
\begin{equation}\label{eq:dirichlet}
\sum_{S\ni i}\widehat h(S)^2=\sigma^2 I_i(h),\qquad
\sum_{S\subseteq J}|S|\widehat h(S)^2=\sigma^2 I(h).
\end{equation}
These identities do not require monotonicity.
The next estimate follows the hypercontractive influence method of
Kahn, Kalai, and Linial~\cite{KKL88}. We prove the biased two-point
inequality directly and use the standard product argument of
Bonami~\cite[Chapter~III, Lemma~1]{Bonami1970}, keeping the dependence
on the edge probability explicit.
\begin{samepage}
\begin{lemma}\label{lem:low-degree}
Let $m\ge2$ be real and let $h:\{0,1\}^J\to\{0,1\}$ satisfy
$I_i(h)\le I(h)/m$ for every $i\in J$. If
\[
k=\frac{\sigma\log m}{64},
\]
then
\begin{equation}\label{eq:low-degree}
\sum_{1\le |S|\le k}\widehat h(S)^2\le m^{-1/4}I(h).
\end{equation}
Every degree cutoff is interpreted literally for integer degrees $|S|$;
in particular, the sum is empty when $k<1$.
\end{lemma}
\end{samepage}
\begin{proof}
We first prove a product norm bound. Put $\rho=\sigma/4$, so
$0<\rho\le1/8$, and define the linear operator $T_\rho$ by
$T_\rho\chi_S=\rho^{|S|}\chi_S$. For one coordinate, the bound
$|\chi_i|\le\sigma^{-1}$ and the second moment identity imply
\[
|\E\chi_i^3|\le\sigma^{-1},\qquad
\E\chi_i^4\le\sigma^{-2}.
\]
For real $a,b$, expansion and
$2|ab^3|\le a^2b^2+b^4$ yield
\begin{align*}
\E(a+\rho b\chi_i)^4
&\le a^4+6\rho^2a^2b^2
+\frac{4\rho^3}{\sigma}|ab^3|
+\frac{\rho^4}{\sigma^2}b^4\\
&\le a^4+\frac{13\sigma^2}{32}a^2b^2
+\frac{9\sigma^2}{256}b^4
\le(a^2+b^2)^2,
\end{align*}
where the last inequality uses $\sigma^2\le1/4$.
To tensorize this inequality, induct on $|J|$, the empty product being
immediate. Write $g=a+b\chi_i$ with $a,b$ functions of the other
coordinates, and set $A=T_\rho a$, $B=T_\rho b$, using the operator on
those coordinates. Apply the scalar inequality pointwise and then the
triangle inequality in $L^2$ to obtain
\[
\|T_\rho g\|_4^2
\le \|A^2+B^2\|_2
\le \|A\|_4^2+\|B\|_4^2
\le \|a\|_2^2+\|b\|_2^2
=\|g\|_2^2.
\]
The penultimate inequality is the induction hypothesis. We have proved
\begin{equation}\label{eq:noise-norm}
\|T_\rho g\|_4\le\|g\|_2
\end{equation}
on every finite product.
For any real $d\ge0$, let $P_{\le d}$ be the orthogonal projection onto
the span of the characters of degree at most $d$. If $u=P_{\le d}u$,
the operator $T_\rho$ is invertible and Parseval gives
\[
\|T_\rho^{-1}u\|_2^2
=\sum_{|S|\le d}\rho^{-2|S|}\widehat u(S)^2
\le\rho^{-2d}\|u\|_2^2.
\]
Applying \eqref{eq:noise-norm} to $T_\rho^{-1}u$ proves
$\|u\|_4\le\rho^{-d}\|u\|_2$. Duality in this finite-dimensional
subspace, followed by H\"older's inequality, now gives for every real
function $v$
\begin{equation}\label{eq:projection-norm}
\|P_{\le d}v\|_2
=\sup_{\substack{u=P_{\le d}u\\\|u\|_2=1}}|\E[vu]|
\le\rho^{-d}\|v\|_{4/3}.
\end{equation}
If $k<1$, \eqref{eq:low-degree} is immediate, so assume $k\ge1$.
Since $|\Delta_i h|$ is the indicator of a pivotal event,
$\|\Delta_i h\|_{4/3}=I_i(h)^{3/4}$. Every nonempty Fourier set is
counted at least once when summing over its coordinates. The derivative
coefficient identity and \eqref{eq:projection-norm}, applied on
$J\setminus\{i\}$ with $d=k$, therefore show
\begin{align*}
\sum_{1\le |S|\le k}\widehat h(S)^2
&\le\sum_{i\in J}\sum_{\substack{S\ni i\\|S|\le k}}
\widehat h(S)^2\\
&=\sigma^2\sum_{i\in J}
\sum_{\substack{A\subseteq J\setminus\{i\}\\|A|\le k-1}}
\widehat{\Delta_i h}(A)^2\\
&\le\sigma^2\rho^{-2k}\sum_{i\in J}I_i(h)^{3/2}.
\end{align*}
The function $s\mapsto s\log(4/s)$ is increasing on $(0,1/2]$, since
its derivative is $\log(4/s)-1>0$. 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\le1<m^{-1/4}I(h).
\]
This proves the estimate for every $0<p<1$, without a lower bound on
$\sigma$.
\end{proof}
==== END A-Sharp-Threshold-Bound-for-Monotone-Graph-Properties//fourier.tex ====
==== BEGIN A-Sharp-Threshold-Bound-for-Monotone-Graph-Properties//graph.tex ====
\section{Restricting to the edges incident with a vertex block}
\label{sec:graph}
Let $E_n=\binom{[n]}2$ be the edge set of the complete graph on $[n]$,
and let $f\colon\{0,1\}^{E_n}\to\{0,1\}$ be invariant under vertex
permutations. Fix $p\in(0,1)$ and put $\sigma=\sqrt{p(1-p)}$.
All Fourier coefficients, variances, and influences in this section
use this bias. Monotonicity is not needed.
The purpose of a vertex block is to connect two different notions of
degree. A restriction to the edges incident with the block retains
enough symmetry to apply Lemma~\ref{lem:low-degree}. If the block meets
the nonisolated vertices of a Fourier support at just one vertex $u$,
then the surviving Fourier degree is the graph degree of $u$.
An $s$-edge graph with $s\ge1$ has a nonisolated vertex of degree at most
$\sqrt{2s}$. Thus a bound for conditional Fourier degrees up to $k$
will control original degrees up to $k^2/2$.
The restriction identity is the biased-product form of the standard
Fourier restriction identity; compare
\cite[arXiv version~2, Lemma~2.7]{KKLMS20}.
We include its short proof. The next identities hold for every Boolean
$f$, without a symmetry assumption.
\begin{lemma}[Exact averaging over a restriction]
\label{lem:restriction}
Let $F\subseteq E_n$, put $H=E_n\setminus F$, and, for
$y\in\{0,1\}^{H}$, let $f_y(x)=f(x,y)$ for
$x\in\{0,1\}^{F}$. If $y$ has the Bernoulli-$p$ product law, then,
for every real $k>0$,
\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 v2<v^2/2$, its
average degree over these vertices satisfies
\[
\frac{2s}{v}<\sqrt{2s}.
\]
Choose a vertex $u\in V(S)$ whose degree $d_S(u)$ is at most this average. Then
\begin{equation}
1\le d_S(u)\le\sqrt{2s}\le k,
\qquad v\le2s\le k^2.
\label{eq:support-degree}
\end{equation}
Choose $B$ uniformly among the $m$-element vertex sets. Conditioned
on $u\in B$, each other specified vertex belongs to $B$ with
probability $(m-1)/(n-1)$. A union bound gives
\begin{equation}
\Pr_B\{B\cap V(S)=\{u\}\}
\ge \frac mn
\left(1-(v-1)\frac{m-1}{n-1}\right).
\label{eq:one-vertex-event}
\end{equation}
On this event, $S\cap F_B$ consists of \emph{every} support edge
incident with $u$, and contains no other support edge. Its size is
therefore $d_S(u)$, between $1$ and $k$; it need not be $1$.
Figure~\ref{fig:block} illustrates this distinction.
\input{figures/block}
To bound the probability uniformly in $p$, note that $k\le t$ and
\[
\frac{m-1}{n-1}\le\frac1{\sqrt n},
\qquad
(v-1)\frac{m-1}{n-1}
\le t^2e^{-t/2}\le256e^{-8}<\frac12.
\]
Here $t^2e^{-t/2}$ is decreasing for $t\ge16$.
Consequently, for every support under consideration,
\begin{equation}
\Pr_B\{1\le|S\cap F_B|\le k\}\ge\frac{m}{2n}.
\label{eq:support-detection}
\end{equation}
The choice of $u$ may depend on $S$. The lower bound
\eqref{eq:support-detection} is applied to each nonnegative summand
$\widehat f(S)^2$ separately; no block must capture all supports
simultaneously. Comparing with \eqref{eq:block-average} and
cancelling $m/(2n)$ proves \eqref{eq:captured-mass}.
If $k^2/2<1$, the sum in \eqref{eq:captured-mass} is empty and the
conclusion holds without choosing a support.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{thm:variance}]
First suppose $t=\log n\ge16$, and choose $m$ and $k$ as in
Lemma~\ref{lem:block-capture}; in particular $m\ge3$ and $k>0$.
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 n<e^{16}$, the same Fourier identities immediately
give
\[
\Var(f)\le\sigma^2I(f)\le\frac14 I(f)
\le\frac{64}{(\log n)^2}I(f).
\]
Hence the single choice $C_0=2^{17}$ works for every integer $n\ge2$
and every $p\in(0,1)$, as asserted.
\end{proof}
==== END A-Sharp-Threshold-Bound-for-Monotone-Graph-Properties//graph.tex ====
==== BEGIN A-Sharp-Threshold-Bound-for-Monotone-Graph-Properties//introduction.tex ====
\section{Introduction}
\label{sec:introduction}
For an integer $n\ge2$, write $[n]=\{1,\ldots,n\}$ and let $E_n=\binom{[n]}2$ be the edge set of the complete simple graph on $n$ vertices. We identify a graph with an element of $\{0,1\}^{E_n}$. A \emph{graph property} is a family $\mathcal P\subseteq\{0,1\}^{E_n}$ invariant under every permutation of $[n]$. It is \emph{increasing}, or \emph{monotone}, if adding edges preserves membership, and \emph{nontrivial} if it is neither empty nor the whole space.
Write $\mu_p(\mathcal P)$ for the probability that a graph whose edges are present independently with probability $p$ belongs to $\mathcal P$. For $0<a<1$, define
\[
p_a(\mathcal P)=\inf\{p\in[0,1]:\mu_p(\mathcal P)\ge a\}.
\]
All logarithms in this paper are natural. In particular, $n$ always counts vertices, not edge coordinates.
\begin{theorem}[Friedgut--Kalai sharp-threshold conjecture]
\label{thm:threshold}
For every integer $n\ge2$, every nontrivial increasing family $\mathcal P$ of graphs on $n$ vertices invariant under all vertex permutations, and every $0<\varepsilon<1/2$,
\begin{equation}
\label{eq:threshold}
p_{1-\varepsilon}(\mathcal P)-p_\varepsilon(\mathcal P)
\le \frac{2^{19}}{(\log n)^2}\log\frac1{2\varepsilon}.
\end{equation}
\end{theorem}
The influence theorem of Kahn, Kalai, and Linial~\cite{KKL88}
connected Fourier analysis with the sensitivity of Boolean functions
to individual coordinates. Bourgain, Kahn, Kalai, Katznelson, and
Linial extended the influence theorem to product
spaces~\cite{BKKKL92}. Friedgut and Kalai combined that extension
with the Margulis--Russo probability-derivative identity to show that
every increasing family invariant under a transitive coordinate group
has a narrow transition~\cite[Section~2]{FK96}. For graph properties,
vertex permutations act transitively on the edge coordinates, and their
theorem gives the universal width bound
$C\log(1/(2\varepsilon))/\log n$~\cite[Theorem~1.1]{FK96}.
They conjectured the denominator $(\log n)^2$ with the same dependence
on $\varepsilon$~\cite[Conjecture~1.2]{FK96}.
Theorem~\ref{thm:threshold} resolves that conjecture positively;
its numerical constant is only a convenient explicit choice.
The squared logarithm is the optimal order in $n$ when
$\varepsilon$ is fixed. Friedgut and Kalai already pointed to the
property of containing a clique with order proportional to $\log n$:
its transition width can be of order $(\log n)^{-2}$
\cite[p.~2994]{FK96}.
Bourgain and Kalai went beyond coordinate transitivity by using the
action of the symmetry group on sets of coordinates~\cite{BK97}.
For every fixed $\eta>0$ 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 $0<p<1$,
\begin{equation}
\label{eq:variance}
\Var_p(f)\le\frac{2^{17}}{(\log n)^2}I_p(f).
\end{equation}
No monotonicity assumption is needed.
\end{theorem}
At the unbiased measure, Kelman, Kindler, Lifshitz, Minzer, and Safra
proved the graph-symmetric estimate
\[
I_{1/2}(f)\ge
c\,\frac{(\log n)^2}{(\log\log n)^2}\Var_{1/2}(f)
\]
for all sufficiently large $n$ and an absolute $c>0$
\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 $0<p<1$, including for nonmonotone properties.
Random restrictions and symmetry of Fourier coefficients are central
to the arguments of Bourgain--Kalai and
Kelman--Kindler--Lifshitz--Minzer--Safra~\cite{BK97,KKLMS20}.
Here the restriction is chosen through the vertices: leave free all
edges touching a random block $B$ of about $\sqrt n$ vertices, while
conditioning on every other edge. Permutations inside $B$ survive
every such conditioning. Their edge orbits bound each conditional
influence, to which an elementary Fourier estimate applies.
The resulting estimate is linear in total influence, so it can be
averaged over the conditioned coordinates. Section~\ref{sec:fourier}
proves this estimate directly, including its dependence on the bias.
The second ingredient regards each edge set indexing a Fourier
coefficient as a graph. Any nonempty such graph with at most $k^2/2$
edges has a nonisolated vertex of degree at most $k$. With sufficient
probability, $B$ meets its nonisolated vertices only at that vertex.
The restriction then leaves between one and $k$ edges of this graph
free. This turns control of conditional Fourier degrees up to $k$
into control of original degrees up to $k^2/2$. Taking $k$ proportional
to $\sqrt{p(1-p)}\log n$ yields \eqref{eq:variance}; the bias factor
cancels in the estimate for the remaining Fourier degrees.
Section~\ref{sec:threshold} then integrates the probability derivative
to obtain the full quantile bound.
==== END A-Sharp-Threshold-Bound-for-Monotone-Graph-Properties//introduction.tex ====
==== BEGIN A-Sharp-Threshold-Bound-for-Monotone-Graph-Properties//main.tex ====
\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[margin=1.03in]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{microtype,graphicx,xcolor}
\usepackage[hyphens]{url}
\usepackage[colorlinks=true,linkcolor=blue!50!black,citecolor=blue!50!black,urlcolor=blue!50!black]{hyperref}
\newcommand{\E}{\mathbb E}
\DeclareMathOperator{\Var}{Var}
\newcommand{\1}{\mathbf 1}
\newcommand{\R}{\mathbb R}
\newcommand{\N}{\mathbb N}
\newcommand{\eps}{\varepsilon}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\numberwithin{equation}{section}
\hypersetup{pdftitle={A Sharp Threshold Bound for Monotone Graph Properties},pdfauthor={OpenAI},pdfsubject={A proof of the Friedgut--Kalai sharp-threshold conjecture}}
\title{A Sharp Threshold Bound for\\Monotone Graph Properties}
\author{OpenAI}
\date{September 25, 2026}
\begin{document}
\maketitle
\begin{abstract}
We prove the Friedgut--Kalai sharp-threshold conjecture. For every integer $n\ge2$, every nontrivial increasing family of graphs on $n$ vertices invariant under all vertex permutations, and every $0<\varepsilon<1/2$, the edge probabilities at which its probability equals $\varepsilon$ and $1-\varepsilon$ differ by at most $C\log(1/(2\varepsilon))/(\log n)^2$, for a universal constant $C$.
\end{abstract}
\input{sections/introduction}
\input{sections/fourier}
\input{sections/graph}
\input{sections/threshold}
\clearpage
\input{references}
\end{document}
==== END A-Sharp-Threshold-Bound-for-Monotone-Graph-Properties//main.tex ====
==== BEGIN A-Sharp-Threshold-Bound-for-Monotone-Graph-Properties//references.tex ====
\begin{thebibliography}{10}
\bibitem{Bonami1970}
Aline Bonami,
\href{https://doi.org/10.5802/aif.357}{\'Etude des coefficients de Fourier
des fonctions de \(L^p(G)\)},
\emph{Annales de l'Institut Fourier}
\textbf{20} (1970), no.~2, 335--402.
\bibitem{BKKKL92}
Jean Bourgain, Jeff Kahn, Gil Kalai, Yitzhak Katznelson, and Nathan Linial,
\href{https://doi.org/10.1007/BF02808010}{The influence of variables
in product spaces},
\emph{Israel Journal of Mathematics}
\textbf{77} (1992), 55--64.
\bibitem{BK97}
Jean Bourgain and Gil Kalai,
\href{https://doi.org/10.1007/s000390050015}{Influences of variables and
threshold intervals under group symmetries},
\emph{Geometric and Functional Analysis}
\textbf{7} (1997), no.~3, 438--461.
\bibitem{Friedgut22}
Ehud Friedgut,
\href{https://doi.org/10.4171/ICM2022/78}{KKL's influence on me},
in \emph{Proceedings of the International Congress of Mathematicians 2022},
Vol.~6, Dmitry Beliaev and Stanislav Smirnov (eds.),
EMS Press, 2023, pp.~4568--4581.
\bibitem{FK96}
Ehud Friedgut and Gil Kalai,
\href{https://doi.org/10.1090/S0002-9939-96-03732-X}{Every monotone graph
property has a sharp threshold},
\emph{Proceedings of the American Mathematical Society}
\textbf{124} (1996), no.~10, 2993--3002.
\bibitem{KKL88}
Jeff Kahn, Gil Kalai, and Nathan Linial,
\href{https://doi.org/10.1109/SFCS.1988.21923}{The influence of variables
on Boolean functions},
in \emph{Proceedings of the 29th Annual Symposium on Foundations of
Computer Science}, IEEE Computer Society, 1988, pp.~68--80.
\bibitem{KKLMS20}
Esty Kelman, Guy Kindler, Noam Lifshitz, Dor Minzer, and Muli Safra,
\href{https://doi.org/10.1007/s00039-020-00544-2}{Towards a proof of the
Fourier--entropy conjecture?},
\emph{Geometric and Functional Analysis}
\textbf{30} (2020), no.~4, 1097--1138.
Accessible preprint:
\href{https://arxiv.org/abs/1911.10579v2}{arXiv:1911.10579v2}, 7 May 2020.
\bibitem{ExpectationEquivalence2026}
OpenAI,
Integral and fractional expectation thresholds are equivalent,
OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Integral-and-fractional-expectation-thresholds-are-equivalent-September-23-2026/paper.pdf}{OAI:Integral-and-fractional-expectation-thresholds-are-equivalent-September-23-2026},
2026.
\bibitem{SecondKahnKalai2026}
OpenAI,
The second Kahn--Kalai conjecture,
OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/The-second-Kahn-Kalai-conjecture-September-24-2026/paper.pdf}{OAI:The-second-Kahn-Kalai-conjecture-September-24-2026},
2026.
\bibitem{Russo81}
Lucio Russo,
\href{https://doi.org/10.1007/BF00535742}{On the critical percolation probabilities},
\emph{Zeitschrift f\"ur Wahrscheinlichkeitstheorie und verwandte Gebiete}
\textbf{56} (1981), no.~2, 229--237.
\end{thebibliography}
==== END A-Sharp-Threshold-Bound-for-Monotone-Graph-Properties//references.tex ====
==== BEGIN A-Sharp-Threshold-Bound-for-Monotone-Graph-Properties//threshold.tex ====
\section{From influence to threshold width}
\label{sec:threshold}
We pass from influence to transition width using the Russo--Margulis
probability-derivative formula; see Russo~\cite[Lemma~3]{Russo81}
and Friedgut--Kalai~\cite[Lemma~2.2]{FK96}. We include the finite
calculation with our pivotal-influence convention and then integrate
the resulting differential inequality.
\begin{proof}[Proof of Theorem~\ref{thm:threshold}]
Put $f=\1_{\mathcal P}$, $\mu(p)=\E_p f$, and $C_0=2^{17}$. We first verify the probability-derivative identity with the influence convention used here. If the edge probabilities are allowed to vary separately, $\E f$ is a multilinear polynomial in those probabilities. Its partial derivative in the probability at $e$ is the expectation of
\[
\Delta_e f=f(x_{e\leftarrow1})-f(x_{e\leftarrow0}).
\]
For increasing $f$, this difference takes values in $\{0,1\}$, so its expectation is $I_{e,p}(f)$ when all other biases are $p$. Differentiating along the diagonal therefore gives
\begin{equation}
\label{eq:russo}
\mu'(p)=I_p(f).
\end{equation}
This is the usual probability-derivative formula underlying the sharp-threshold method; the calculation above proves it directly in the present finite setting.
Since $f$ is Boolean, $\Var_p(f)=\mu(p)(1-\mu(p))$. Theorem~\ref{thm:variance} and \eqref{eq:russo} imply
\begin{equation}
\label{eq:differential}
\mu'(p)\ge \frac{(\log n)^2}{C_0}\mu(p)(1-\mu(p))
\qquad(0<p<1).
\end{equation}
Nontriviality and monotonicity give $f(\varnothing)=0$ and $f(E_n)=1$. Both configurations have positive probability for every interior bias, hence $0<\mu(p)<1$ there, while $\mu(0)=0$ and $\mu(1)=1$. Equation~\eqref{eq:differential} now gives $\mu'(p)>0$ 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 ====