54785de
\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[margin=1.05in]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{microtype}
\usepackage{xcolor}
\usepackage[colorlinks=true,linkcolor=blue!50!black,citecolor=blue!50!black,urlcolor=blue!50!black]{hyperref}
\newcommand{\E}{\mathbb{E}}
\DeclareMathOperator{\Var}{Var}
\newcommand{\one}{\mathbf{1}}
\newcommand{\eps}{\varepsilon}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\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 self-contained proof of the Friedgut--Kalai sharp-threshold conjecture}}
\title{A Sharp Threshold Bound for\\[2pt] Monotone Graph Properties}
\author{OpenAI}
\date{September 25, 2026}
\begin{document}
\maketitle
\begin{abstract}
A monotone graph property is a family of graphs on a fixed vertex set
that is preserved when edges are added, and that ignores the names of the
vertices. As each possible edge is included independently with
probability $p$, the probability that the random graph has the property
rises from $0$ to $1$. The Friedgut--Kalai sharp-threshold conjecture
predicts that this rise is very fast: the width of the transition is at
most a constant times $(\log n)^{-2}$, where $n$ is the number of
vertices. We prove the conjecture. The proof combines two facts. First,
a Fourier estimate shows that a Boolean function whose individual edges
barely matter has most of its variance carried by high Fourier degrees.
Second, a random ``vertex block'' of about $\sqrt n$ vertices converts
information about low Fourier degrees of one restricted function into
information about low Fourier degrees of the original function. Together
these give a variance-versus-influence inequality, and integrating
Russo's identity turns that inequality into the sharp width bound.
Everything is stated and proved from scratch.
\end{abstract}
\section{Introduction}\label{sec:introduction}
Throughout, $n\ge 2$ is an integer and $[n]=\{1,2,\dots,n\}$.
The complete graph on $[n]$ has edge set $E_n=\binom{[n]}{2}$.
A graph is the same thing as a subset of $E_n$, or equivalently as a
$0/1$ vector $x=(x_e)_{e\in E_n}$ where $x_e=1$ means edge $e$ is
present. For $0\le p\le 1$, the \emph{$p$-random graph} has independent
edges with $\Pr(x_e=1)=p$.
\begin{definition}\label{def:property}
A \emph{graph property} is a set $\mathcal P\subseteq\{0,1\}^{E_n}$ of
graphs that is unchanged by relabelling the vertices: if $x\in\mathcal P$
and $\pi$ is any permutation of $[n]$, then the graph with edge indicator
$x_{\{\pi(u),\pi(v)\}}$ in place of $x_{\{u,v\}}$ also belongs to
$\mathcal P$. It is \emph{increasing} (also called \emph{monotone}) if
turning an absent edge into a present edge can never take a graph out of
$\mathcal P$. It is \emph{nontrivial} if it is neither empty nor the set
of all graphs.
\end{definition}
Let $\mu_p(\mathcal P)$ be the probability that the $p$-random graph lies
in $\mathcal P$. An increasing property has $\mu_p$ nondecreasing in $p$.
For $0<a<1$ define the quantile
\[
p_a(\mathcal P)=\inf\{\,p\in[0,1]:\mu_p(\mathcal P)\ge a\,\}.
\]
All logarithms are natural, and $n$ always counts vertices, not edges.
\begin{theorem}[Sharp threshold]\label{thm:threshold}
Let $n\ge 2$, let $\mathcal P$ be a nontrivial increasing graph property
on $n$ vertices, and let $0<\eps<1/2$. Then
\begin{equation}\label{eq:threshold}
p_{1-\eps}(\mathcal P)-p_\eps(\mathcal P)
\le \frac{2^{19}}{(\log n)^2}\,\log\frac{1}{2\eps}.
\end{equation}
\end{theorem}
The exponent $2$ on $\log n$ is the best possible. Friedgut and Kalai
observed that the property ``contains a clique on $c\log n$ vertices''
has a transition whose width is of order $(\log n)^{-2}$
\cite[p.~2994]{FK96}, so no bound with a slower-decaying denominator can
hold for all properties. Friedgut and Kalai proved \eqref{eq:threshold}
with denominator $\log n$ and conjectured the squared logarithm
\cite[Conjecture~1.2]{FK96}. Bourgain and Kalai got arbitrarily close,
proving a bound with denominator $(\log n)^{2-\eta}$ for every fixed
$\eta>0$ \cite{BK97}. Theorem~\ref{thm:threshold} settles the conjecture
with an explicit universal constant.
The influence method goes back to Kahn, Kalai, and Linial \cite{KKL88},
whose estimate was extended to product spaces by Bourgain, Kahn, Kalai,
Katznelson, and Linial \cite{BKKKL92}; Friedgut \cite{Friedgut22} surveys
this line of work. At the single unbiased measure $p=1/2$, Kelman,
Kindler, Lifshitz, Minzer, and Safra proved
$I_{1/2}(f)\ge c\,(\log n)^2/(\log\log n)^2\,\Var_{1/2}(f)$ for all large
$n$ and an absolute constant $c>0$ \cite{KKLMS20}; that controls one bias,
whereas a threshold-width bound must hold across the whole transition,
which is what the variance estimate below supplies.
The engine of the proof is a variance bound. For a Boolean function
$f$ on graphs, its \emph{pivotal influence} at edge $e$ is the
probability that toggling $e$ alone changes $f$, and its
\emph{total influence} is the sum over edges. Write
$x_{e\leftarrow b}$ for the graph $x$ with edge $e$ forced to $b$, and let
the probability be over all edges other than $e$.
\begin{definition}\label{def:influence}
For $f:\{0,1\}^{E_n}\to\{0,1\}$ and $0<p<1$,
\[
I_{e,p}(f)=\Pr_p\!\bigl(f(x_{e\leftarrow 1})\ne f(x_{e\leftarrow 0})\bigr),
\qquad
I_p(f)=\sum_{e\in E_n}I_{e,p}(f).
\]
All probabilities and expectations in the subscript $p$ use the
independent-edge measure with $\Pr(x_e=1)=p$.
\end{definition}
\begin{theorem}[Variance controls influence]\label{thm:variance}
Let $n\ge 2$, let $f:\{0,1\}^{E_n}\to\{0,1\}$ be invariant under vertex
permutations, and let $0<p<1$. Then
\begin{equation}\label{eq:variance}
\Var_p(f)\le \frac{2^{17}}{(\log n)^2}\,I_p(f).
\end{equation}
No monotonicity is assumed.
\end{theorem}
The proof of Theorem~\ref{thm:threshold} from Theorem~\ref{thm:variance}
is short and is done in Section~\ref{sec:threshold}. The rest of the
paper proves Theorem~\ref{thm:variance}.
\paragraph{How the variance bound is proved.}
Think of $f$ as a function on the edges of the complete graph, and expand
it in the Fourier basis adapted to the biased measure. Two different
notions of ``degree'' then appear. There is the \emph{Fourier degree}
$|S|$, the number of edges in a Fourier term, and there is the
\emph{conditional Fourier degree} of $f$ after some edges are frozen.
The difficult part of any sharp-threshold argument is that these two
notions behave very differently. A vertex-symmetric function may have
huge total influence even when no single edge matters much, and then it
is the high Fourier degrees that soak up the variance.
The argument has two independent pieces.
\begin{enumerate}
\item \emph{A Fourier lemma} (Section~\ref{sec:fourier}). If every
single-edge influence of a Boolean $h$ is at most $1/m$ of its total
influence, then the Fourier coefficients of degrees between $1$ and
about $\sigma\log m$ carry at most $m^{-1/4}$ times the total influence.
Here $\sigma=\sqrt{p(1-p)}$ measures the bias. The point is that the
bound is \emph{linear} in the total influence, so it can later be
averaged.
\item \emph{A geometric restriction} (Section~\ref{sec:graph}). Pick a
random set $B$ of about $\sqrt n$ vertices and freeze every edge that
meets $B$ in neither endpoint. Permutations of $B$ survive the freezing,
so piece~1 applies to each restricted function. The gain is a dictionary
between degrees: a Fourier term $S$ of the original function survives
with conditional degree equal to $|S\cap F_B|$, where $F_B$ is the set of
edges touching $B$. Because any small edge set has a low-degree vertex,
we can choose $B$ so that only that vertex of $S$ falls in $B$, and the
surviving degree is small exactly when $|S|$ is not too large.
\end{enumerate}
Combining the two gives \eqref{eq:variance}; Section~\ref{sec:threshold}
finishes the argument.
We record for the reader the two companion papers that treat different
threshold questions and are not used here: the equivalence of integral
and fractional expectation thresholds \cite{ExpectationEquivalence2026},
and the second Kahn--Kalai conjecture \cite{SecondKahnKalai2026}.
\section{A Fourier estimate for Boolean functions with flat influence}
\label{sec:fourier}
This section proves one analytic lemma. It says that if a Boolean
function depends on many coordinates in a balanced way, so that no single
coordinate carries more than a $1/m$ fraction of the total influence,
then its low-degree Fourier coefficients carry very little of the
$L^2$ mass. The statement is linear in the total influence, which is
exactly what the averaging in Section~\ref{sec:graph} will need.
\paragraph{The biased Fourier basis.}
Fix a finite set $J$ of coordinates and a bias $0<p<1$, and put
\[
\sigma=\sqrt{p(1-p)},\qquad 0<\sigma\le\tfrac12.
\]
All expectations and norms in this section are with respect to the
product measure on $\{0,1\}^J$ in which each coordinate equals $1$ with
probability $p$. For $q\ge1$ write $\|g\|_q=(\E|g|^q)^{1/q}$. Define, for
$i\in J$,
\[
\chi_i(x)=\frac{x_i-p}{\sigma},\qquad
\chi_S(x)=\prod_{i\in S}\chi_i(x)\ \ (S\subseteq J),\qquad
\chi_\varnothing=1 .
\]
Each $\chi_i$ has mean $0$ and second moment $1$. Since the coordinates
are independent, the $2^{|J|}$ functions $\chi_S$ are orthonormal:
\[
\E[\chi_S\chi_T]=\one\{S=T\}.
\]
They are $2^{|J|}$ orthonormal vectors in the $2^{|J|}$-dimensional space
of real functions on $\{0,1\}^J$, so they form an orthonormal basis.
Writing the Fourier coefficient of $g$ at $S$ as
$\widehat g(S)=\E[g\,\chi_S]$, we get the expansion and Parseval identity
\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$, let
$\Delta_i g(x)=g(x_{J\setminus\{i\}},1)-g(x_{J\setminus\{i\}},0)$,
a function of the coordinates other than $i$. Averaging the product
$g\,\chi_i$ over the single coordinate $i$ leaves a factor
$p(1-p)/\sigma=\sigma$ times this difference:
\[
\E_i[g\,\chi_i]=\frac{p(1-p)}{\sigma}\,\Delta_i g=\sigma\,\Delta_i g .
\]
Consequently, for $A\subseteq J\setminus\{i\}$, the coefficient of $g$ at
$A\cup\{i\}$ equals $\sigma$ times the coefficient of $\Delta_i g$ at
$A$ (the latter taken on the coordinates $J\setminus\{i\}$):
\begin{equation}\label{eq:derivative}
\widehat g(A\cup\{i\})=\sigma\,\widehat{\Delta_i g}(A).
\end{equation}
For a Boolean $h:\{0,1\}^J\to\{0,1\}$, define the influence of coordinate
$i$ and the total influence by
\[
I_i(h)=\Pr(\Delta_i h\ne0),\qquad I(h)=\sum_{i\in J}I_i(h).
\]
Because $\Delta_i h\in\{-1,0,1\}$, it satisfies
$|\Delta_i h|=\one\{\Delta_i h\ne0\}$ and so
$\|\Delta_i h\|_{4/3}=I_i(h)^{3/4}$. Applying Parseval on the coordinates
$J\setminus\{i\}$ to \eqref{eq:derivative} gives the derivatives of the
squared mass, and summing over $i$ gives the two identities
\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 hold for every Boolean $h$; no monotonicity is used anywhere in
this section.
\paragraph{The noise operator and hypercontractivity.}
The proof of the low-degree bound goes through a smoothing operator. For
$0<\rho\le1$ define the linear operator $T_\rho$ on functions on
$\{0,1\}^J$ by its action on the basis,
\[
T_\rho\chi_S=\rho^{|S|}\chi_S .
\]
In other words, $T_\rho$ multiplies each Fourier coefficient of degree
$d$ by $\rho^{d}$. The following lemma is the standard hypercontractive
estimate of Bonami \cite{Bonami1970}, proved here for a general bias so
that the dependence on $\sigma$ is explicit.
\begin{lemma}[Hypercontractive norm bound]\label{lem:noise}
For every real function $g$ on $\{0,1\}^J$ and $\rho=\sigma/4$,
\[
\|T_\rho g\|_4\le\|g\|_2 .
\]
\end{lemma}
\begin{proof}
Since $0<\sigma\le1/2$ we have $0<\rho\le1/8$. It is enough to handle a
single coordinate and then tensorize.
\emph{One coordinate.} The bound $|\chi_i|\le\sigma^{-1}$ and
$\E\chi_i^2=1$ give $|\E\chi_i^3|\le\sigma^{-1}$ and
$\E\chi_i^4\le\sigma^{-2}$. For real numbers $a,b$, expand
$\E(a+\rho b\,\chi_i)^4$ and bound the odd term using
$2|ab^3|\le a^2b^2+b^4$:
\[
\begin{aligned}
\E(a+\rho b\,\chi_i)^4
&=a^4+6\rho^2a^2b^2+4\rho^3ab^3\,\E\chi_i^3+\rho^4b^4\,\E\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+6\rho^2a^2b^2+\frac{2\rho^3}{\sigma}\bigl(a^2b^2+b^4\bigr)+\frac{\rho^4}{\sigma^2}b^4 .
\end{aligned}
\]
Substituting $\rho=\sigma/4$, the coefficient of $a^2b^2$ is
$6\rho^2+2\rho^3/\sigma=6\sigma^2/16+2\sigma^2/64=13\sigma^2/32$, and the
coefficient of $b^4$ is $2\rho^3/\sigma+\rho^4/\sigma^2=\sigma^2/32+\sigma^2/256=9\sigma^2/256$.
Hence
\[
\E(a+\rho b\,\chi_i)^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,
\]
where the last step uses $\sigma^2\le1/4$, which makes
$\frac{13}{32}\sigma^2\le\frac{13}{128}<2$ and
$\frac{9}{256}\sigma^2\le\frac{9}{1024}<1$.
\emph{Tensorization.} Induct on $|J|$; the empty product is trivial.
Pick a coordinate $i$ and write $g=a+b\,\chi_i$ where $a,b$ depend only on
the other coordinates. Let $A=T_\rho a$ and $B=T_\rho b$ be the images
under $T_\rho$ on those other coordinates, so that
$T_\rho g=A+\rho B\,\chi_i$. Fix the other coordinates; the
single-coordinate inequality, applied to the numbers $A$ and $B$, gives
\[
\E_i\bigl[(T_\rho g)^4\bigr]
=\E_i(A+\rho B\,\chi_i)^4\le(A^2+B^2)^2 .
\]
Let $X=\E_i[(T_\rho g)^4]$, a function of the other coordinates, so
$X\le(A^2+B^2)^2$ pointwise. Since $\|T_\rho g\|_4^2=(\E X)^{1/2}$ and
$\|f^2\|_1=\|f\|_2^2$,
\[
\|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,
\]
where the third step is the induction hypothesis applied to $a$ and $b$,
and the last equality is Parseval, valid because $a,b$ are functions of the
coordinates other than $\chi_i$. Taking square roots gives
$\|T_\rho g\|_4\le\|g\|_2$.
\end{proof}
\paragraph{From the norm bound to low degrees.}
Let $P_{\le d}$ denote the orthogonal projection onto the span of the
characters of degree at most $d$, i.e. $P_{\le d}g=\sum_{|S|\le d}
\widehat g(S)\chi_S$. On that span, $T_\rho$ is invertible with inverse
given by $T_\rho^{-1}\chi_S=\rho^{-|S|}\chi_S$. If $u=P_{\le d}u$, then
by Parseval
\begin{equation}\label{eq:inverse-norm}
\|T_\rho^{-1}u\|_2^2
=\sum_{|S|\le d}\rho^{-2|S|}\widehat u(S)^2
\le\rho^{-2d}\|u\|_2^2 .
\end{equation}
Applying Lemma~\ref{lem:noise} to $T_\rho^{-1}u$ gives
$\|u\|_4=\|T_\rho(T_\rho^{-1}u)\|_4\le\|T_\rho^{-1}u\|_2\le\rho^{-d}\|u\|_2$.
Finally, duality in the finite-dimensional subspace and Holder's
inequality give, 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}}\bigl|\E[vu]\bigr|
\le\rho^{-d}\|v\|_{4/3}.
\end{equation}
\begin{lemma}[Low-degree bound]\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$. Put
\[
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}
Degrees are integers $|S|$, so the sum is empty (and the bound trivial)
when $k<1$.
\end{lemma}
\begin{proof}
If $k<1$ the sum is empty. Assume $k\ge1$. Every nonempty Fourier set is
counted at least once when we sum over its coordinates, so
\[
\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 .
\]
Fix $i$. By \eqref{eq:derivative}, $\widehat h(S)^2$ for $S=A\cup\{i\}$
with $|A|=|S|-1\le k-1$ equals $\sigma^2\widehat{\Delta_i h}(A)^2$. The
inner sum is therefore $\sigma^2$ times the squared $L^2$ norm of the
projection of $\Delta_i h$ onto degrees at most $k-1$ on
$J\setminus\{i\}$. Applying \eqref{eq:projection-norm} with $d=k-1\le k$
and $v=\Delta_i h$,
\[
\sum_{\substack{A\subseteq J\setminus\{i\}\\ |A|\le k-1}}
\widehat{\Delta_i h}(A)^2
\le\rho^{-2(k-1)}\|\Delta_i h\|_{4/3}^2
\le\rho^{-2k}\,I_i(h)^{3/2}.
\]
Summing over $i$ and using \eqref{eq:derivative}'s factor $\sigma^2$,
\begin{equation}\label{eq:low-degree-mid}
\sum_{1\le|S|\le k}\widehat h(S)^2
\le\sigma^2\rho^{-2k}\sum_{i\in J}I_i(h)^{3/2}.
\end{equation}
We bound the two factors. First, since $\rho=\sigma/4$,
\[
\rho^{-2k}=\Bigl(\frac{4}{\sigma}\Bigr)^{2k}
=\exp\!\Bigl(2k\log\frac{4}{\sigma}\Bigr)
=\exp\!\Bigl(\frac{\sigma\log m}{32}\log\frac{4}{\sigma}\Bigr)
=m^{\,\sigma\log(4/\sigma)/32}.
\]
The function $s\mapsto s\log(4/s)$ is increasing on $(0,1/2]$, because its
derivative $\log(4/s)-1$ is positive there. Hence, as $\sigma\le1/2$,
\[
\sigma\log\frac{4}{\sigma}\le\tfrac12\log 8<2,
\qquad\text{so}\qquad
\rho^{-2k}\le m^{1/16}.
\]
Second, split on the size of $I(h)$. If $I(h)\le m^{1/4}$, then
$I_i(h)\le I(h)/m$ gives $I_i(h)^{3/2}=I_i(h)\sqrt{I_i(h)}\le I_i(h)\sqrt{I(h)/m}$,
and summing over $i$,
\[
\sum_{i\in J}I_i(h)^{3/2}\le\sqrt{\frac{I(h)}{m}}\,I(h)\le m^{-3/8}I(h).
\]
Inserting both bounds into \eqref{eq:low-degree-mid} and using
$\sigma^2\le1/4\le1$,
\[
\sum_{1\le|S|\le k}\widehat h(S)^2
\le\sigma^2\,m^{1/16}\,m^{-3/8}I(h)
=\sigma^2\,m^{-5/16}I(h)\le m^{-1/4}I(h),
\]
since $-5/16<-1/4$. If instead $I(h)>m^{1/4}$, then by Parseval and the
Boolean range $0\le h\le1$,
\[
\sum_{1\le|S|\le k}\widehat h(S)^2\le\E h^2\le1<m^{-1/4}\,I(h).
\]
Either way \eqref{eq:low-degree} holds, for every $0<p<1$ and with no
lower bound on $\sigma$.
\end{proof}
\section{Restricting to the edges incident with a vertex block}
\label{sec:graph}
We now exploit the vertex symmetry of $f$. Fix $p\in(0,1)$ and
$\sigma=\sqrt{p(1-p)}$; from here to the end of the section all Fourier
coefficients, variances, and influences use the bias $p$ on
$E_n=\binom{[n]}{2}$, and $f:\{0,1\}^{E_n}\to\{0,1\}$ is invariant under
every permutation of $[n]$. Monotonicity is never used.
\paragraph{Two kinds of degree.}
Lemma~\ref{lem:low-degree} controls Fourier degrees of a restricted
function, but we need a statement about Fourier degrees of $f$ itself.
The bridge is a random set $B$ of vertices. Consider the set of edges
\[
F_B=\{e\in E_n: e\cap B\ne\varnothing\}
\]
that touch $B$; these are the \emph{free} edges. We freeze every edge in
the complement $H_B=E_n\setminus F_B$, i.e. every edge with both
endpoints outside $B$. For a fixed freezing $y\in\{0,1\}^{H_B}$, let
$f_y$ be the resulting function of the free coordinates
$x\in\{0,1\}^{F_B}$, namely $f_y(x)=f(x,y)$.
Two things make this choice useful. First, a permutation of the vertices
of $B$, extended by the identity elsewhere, fixes every edge of $H_B$
(they avoid $B$), so it fixes $y$ and acts only on free coordinates.
Thus $f_y$ inherits the full vertex symmetry of $f$ on the block $B$,
even when the frozen graph $y$ has no symmetry at all. Second, the free
set is not a thin slice of the edges: for a Fourier support $S$ for which
$B$ meets the nonisolated vertex set $V(S)$ in exactly one vertex $u$, the
surviving part
$S\cap F_B$ consists exactly of the edges of $S$ incident with $u$, so
its size is the graph degree $d_S(u)$.
The plan is therefore: pick $B$ so that it captures a single low-degree
vertex of $S$. If $S$ has $s$ edges, some nonisolated vertex of $S$ has
degree at most $\sqrt{2s}$, so a set $S$ with $s\le k^2/2$ has a vertex
of degree at most $k$. Then the conditional Fourier degree of $f_y$ at
$S$ is at most $k$, and Lemma~\ref{lem:low-degree} applies. We make this
precise below.
\paragraph{Exact averaging over a restriction.}
The first tool is an identity relating the Fourier coefficients of the
restricted functions $f_y$ to those of $f$. It holds for every Boolean
$f$ and uses no symmetry.
\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)$ with $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 on $E_n$ and integrate the free
coordinates $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),
\]
because the product $\chi_{A\cup D}$ splits as $\chi_A(x)\chi_D(y)$ and
$\chi_A$ is averaged out against the coefficient. Orthonormality of the
$\chi_D$ on the exterior coordinates $H$ then gives
$\E_y\widehat{f_y}(A)^2=\sum_{D\subseteq H}\widehat f(A\cup D)^2$.
Summing over all $A$ with $1\le|A|\le k$ produces
\eqref{eq:restriction-mass}. Notice that the exterior degree $|D|$ is
completely unconstrained: $S=A\cup D$ may have any size as long as
$|S\cap F|=|A|$ lies between $1$ and $k$.
For the influence identity, note that for $e\in F$ the pivotal event of
$f_y$ at $e$ is the pivotal event of $f$ at $e$ with the exterior
coordinates fixed to $y$. Averaging over $y$ and over the remaining free
coordinates counts the same pivotal event of $f$, so
$\E_y I_e(f_y)=I_e(f)$ for each $e\in F$. Summation over $e\in F$ proves
\eqref{eq:restriction-influence}.
\end{proof}
\paragraph{The block estimate.}
Fix $m$ with $3\le m\le n$, and let $B$ be uniformly random among the
$m$-element subsets of $[n]$. The free set is $F_B$, as above. The point
of the next proposition is to apply Lemma~\ref{lem:low-degree} to $f_y$
for each freezing $y$ and then average.
\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:e\cap B\ne\varnothing\}$ together with
\[
k=\frac{\sigma\log m}{64}.
\]
Then
\begin{equation}\label{eq:block-average}
\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).
\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$: the $\binom m2$ edges inside $B$ and, for each vertex $w\notin B$,
the $m$ edges from $w$ to $B$. Every permutation of $B$, extended by the
identity on $[n]\setminus B$, fixes each edge of $H_B$ individually and
hence fixes $y$. So $f_y$ is invariant under the permutation group of
$B$, even if the graph encoded by $y$ has no symmetry.
These permutations partition $F_B$ into orbits: one orbit of size
$\binom m2$ (the edges inside $B$) and, for each fixed $w\in[n]\setminus
B$, one orbit of size $m$ (the edges $\{u,w\}$, $u\in B$). Since $m\ge3$,
every orbit has size at least $m$. The measure is a product law and
pivotal events are permuted, so $I_e(f_y)$ is constant on each orbit.
If the orbits are $O_1,\dots,O_t$ with sizes $s_j\ge m$ and common
influence $c_j=I_{e}(f_y)$ for $e\in O_j$, then
\[
I(f_y)=\sum_{j=1}^t s_j c_j\ge s_j c_j\ge m\,c_j ,
\]
so $c_j\le I(f_y)/m$. Hence
\[
I_e(f_y)\le\frac{I(f_y)}{m}\qquad(e\in F_B).
\]
Now apply Lemma~\ref{lem:low-degree} to the restricted function $f_y$ on
the coordinates $F_B$: its hypothesis holds, and its conclusion reads
\[
\sum_{\substack{A\subseteq F_B\\ 1\le|A|\le k}}\widehat{f_y}(A)^2
\le m^{-1/4}\,I(f_y).
\]
The right-hand side is linear in $I(f_y)$, so averaging over $y$ 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$. A fixed edge $e$ lies in $F_B$ exactly when at
least one of its two endpoints lies in $B$, which happens with probability
at most $2m/n$ by a union bound. Thus
$\E_B\sum_{e\in F_B}I_e(f)=\sum_e\Pr_B(e\in F_B)I_e(f)\le\frac{2m}{n}I(f)$,
and \eqref{eq:block-average} follows.
\end{proof}
\paragraph{Capturing low Fourier degrees.}
Proposition~\ref{prop:block} only sees Fourier terms whose intersection
with $F_B$ is a between $1$ and $k$ edges. The next lemma shows that this
happens with uniformly positive probability for every small support $S$,
by choosing $B$ to meet $V(S)$ at a single low-degree vertex.
\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}\label{eq:captured-mass}
\sum_{\substack{S\subseteq E_n\\ 1\le|S|\le k^2/2}}\widehat f(S)^2
\le 4\,m^{-1/4}\,I(f).
\end{equation}
\end{lemma}
\begin{proof}
Fix a nonempty $S\subseteq E_n$ with $s=|S|\le k^2/2$, and view $S$ 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$, the average of
$d_S$ over $V(S)$ equals $2s/v<\sqrt{2s}$, so some nonisolated vertex
$u\in V(S)$ has degree at most this average:
\begin{equation}\label{eq:support-degree}
1\le d_S(u)\le\sqrt{2s}\le k,
\qquad v\le2s\le k^2 .
\end{equation}
Choose $B$ uniformly among the $m$-element vertex sets. The event
$B\cap V(S)=\{u\}$ has $u\in B$ and no other vertex of $V(S)$ in $B$.
Given $u\in B$, the other $m-1$ members of $B$ are a random
$(m-1)$-subset of the $n-1$ remaining vertices, so a union bound gives
\begin{equation}\label{eq:one-vertex-event}
\Pr_B\{B\cap V(S)=\{u\}\}
\ge \frac mn\Bigl(1-(v-1)\frac{m-1}{n-1}\Bigr).
\end{equation}
On this event the set $S\cap F_B$ consists exactly of the edges of $S$
incident with $u$, so $|S\cap F_B|=d_S(u)$, which lies in $[1,k]$ by
\eqref{eq:support-degree}.
We bound the probability uniformly in $p$. First $k\le t$, because
$k=\sigma\log m/64\le\frac12\log m/64\le\frac12(t/2)/64<t$. Hence
$v\le k^2\le t^2$. Also
\[
\frac{m-1}{n-1}\le\frac{1}{\sqrt n},
\]
since $m\le\sqrt n$ gives $m-1\le\sqrt n-1=\frac{n-1}{\sqrt n+1}\le
\frac{n-1}{\sqrt n}$. Therefore
\[
(v-1)\frac{m-1}{n-1}\le t^2\cdot\frac{1}{\sqrt n}
=t^2e^{-t/2}\le256\,e^{-8}<\tfrac12,
\]
where $t^2e^{-t/2}$ is decreasing for $t\ge16$ and so is at most its value
$256e^{-8}$ at $t=16$. Combining \eqref{eq:one-vertex-event} with this
bound,
\begin{equation}\label{eq:support-detection}
\Pr_B\{1\le|S\cap F_B|\le k\}\ge\frac mn\cdot\frac12=\frac{m}{2n},
\end{equation}
for every support under consideration.
Now apply \eqref{eq:support-detection} summand by summand. The choice of
$u$ depends on $S$, but the bound is uniform, so for each
$\widehat f(S)^2\ge0$,
\[
\widehat f(S)^2\le\frac{2n}{m}\Pr_B\{1\le|S\cap F_B|\le k\}\widehat f(S)^2 .
\]
Summing over the finitely many $S$ with $1\le|S|\le k^2/2$, comparing with
\eqref{eq:block-average}, and cancelling the common factor,
\[
\sum_{\substack{S\subseteq E_n\\ 1\le|S|\le k^2/2}}\widehat f(S)^2
\le\frac{2n}{m}\cdot\frac{2m}{n}\,m^{-1/4}I(f)
=4\,m^{-1/4}I(f).
\]
If $k^2/2<1$ the sum is empty and the conclusion is vacuous.
\end{proof}
\paragraph{Proof of the variance bound.}
We now assemble the two estimates.
\begin{proof}[Proof of Theorem~\ref{thm:variance}]
First suppose $t=\log n\ge16$, and take $m=\lfloor\sqrt n\rfloor$ and
$k=\sigma\log m/64$ as in Lemma~\ref{lem:block-capture}; then $m\ge3$ and
$k>0$. The high Fourier degrees are controlled directly from the Dirichlet
identity \eqref{eq:dirichlet}. Since $|S|>k^2/2$ implies $1<2|S|/k^2$,
\begin{equation}\label{eq:graph-tail}
\sum_{|S|>k^2/2}\widehat f(S)^2
\le\frac{2}{k^2}\sum_{S\subseteq E_n}|S|\,\widehat f(S)^2
=\frac{2\sigma^2}{k^2}\,I(f).
\end{equation}
Combine Parseval \eqref{eq:parseval}, the captured mass
\eqref{eq:captured-mass}, and this tail \eqref{eq:graph-tail}:
\begin{equation}\label{eq:graph-variance-preconstant}
\Var(f)=\sum_{\varnothing\ne S}\widehat f(S)^2
\le\Bigl(4\,m^{-1/4}+\frac{2\sigma^2}{k^2}\Bigr)I(f).
\end{equation}
It remains to bound the bracketed constant. Because $m\ge\sqrt n/2$ and
$t\ge16$, we have $\log m\ge t/2-\log2\ge t/3$, so
\[
\frac{2\sigma^2}{k^2}
=\frac{2\sigma^2}{(\sigma\log m/64)^2}
=\frac{8192}{(\log m)^2}
\le\frac{73728}{t^2},
\]
an exact cancellation of $\sigma^2$ that holds even when $p$ is close to
$0$ or $1$. For the other term, $m^{-1/4}\le(\sqrt n/2)^{-1/4}
=2^{1/4}n^{-1/8}=2^{1/4}e^{-t/8}$, and $t^2e^{-t/8}$ is nonincreasing for
$t\ge16$, so
\[
4\,m^{-1/4}t^2\le4\cdot2^{1/4}\,t^2e^{-t/8}
\le4\cdot2^{1/4}\cdot256\,e^{-2}<256 .
\]
Thus $4m^{-1/4}\le256/t^2$ and the right-hand side of
\eqref{eq:graph-variance-preconstant} is at most
$(73728+256)I(f)/t^2\le2^{17}I(f)/(\log n)^2$, proving \eqref{eq:variance}.
If instead $2\le n<e^{16}$, the Fourier identities give immediately
\[
\Var(f)\le\sigma^2 I(f)\le\tfrac14 I(f)\le\frac{64}{(\log n)^2}I(f),
\]
because $\sigma^2\le1/4$ and $(\log n)^2<256$. Hence the single constant
$C_0=2^{17}$ works for every integer $n\ge2$ and every $p\in(0,1)$.
\end{proof}
\section{From influence to threshold width}\label{sec:threshold}
This short section turns Theorem~\ref{thm:variance} into
Theorem~\ref{thm:threshold} by integrating the probability derivative.
The key formula is due to Russo~\cite[Lemma~3]{Russo81} and is used in
the same way by Friedgut and Kalai~\cite[Lemma~2.2]{FK96}.
\begin{proof}[Proof of Theorem~\ref{thm:threshold}]
Let $f=\one_{\mathcal P}$ be the indicator of an increasing graph
property, let $\mu(p)=\E_p f$ be the probability that the $p$-random graph
lies in $\mathcal P$, and put $C_0=2^{17}$.
\emph{Russo's identity.} If the edge probabilities are allowed to vary
independently, $\E f$ is a multilinear polynomial in the $|E_n|$
individual edge probabilities. Differentiating in the probability of a
single edge $e$ gives the expectation of the discrete difference
$\Delta_e f=f(x_{e\leftarrow1})-f(x_{e\leftarrow0})$, all other
coordinates retaining their probabilities. For an increasing $f$, the
difference $f(x_{e\leftarrow1})-f(x_{e\leftarrow0})$ takes only the values
$0$ and $1$, so its expectation, with all other biases set to $p$, is
exactly the pivotal influence $I_{e,p}(f)$ of Definition~\ref{def:influence}.
Summing the partial derivatives along the diagonal where every edge has
probability $p$ therefore gives
\begin{equation}\label{eq:russo}
\mu'(p)=I_p(f).
\end{equation}
\emph{The differential inequality.} Since $f$ is Boolean,
$\Var_p(f)=\mu(p)(1-\mu(p))$. Theorem~\ref{thm:variance} together with
\eqref{eq:russo} gives
\begin{equation}\label{eq:differential}
\mu'(p)\ \ge\ \frac{(\log n)^2}{C_0}\,\mu(p)\bigl(1-\mu(p)\bigr)
\qquad(0<p<1).
\end{equation}
\emph{Quantiles are well defined.} Nontriviality and monotonicity give
$f(\varnothing)=0$ and $f(E_n)=1$, and both graphs have positive
probability under every interior bias, so $0<\mu(p)<1$ for $0<p<1$ while
$\mu(0)=0$ and $\mu(1)=1$. By continuity $\mu$ has a unique interior
crossing $\mu(p_a)=a$ for every $0<a<1$. Thus each quantile $p_a$ is a
genuine interior point, and on the interval $[p_\eps,p_{1-\eps}]$ the
division in \eqref{eq:differential} is legitimate:
\[
\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}.
\]
\emph{Integration.} The log-odds rise with slope at least
$(\log n)^2/C_0$ across $[p_\eps,p_{1-\eps}]$. At the endpoints the odds
are $(1-\eps)/\eps$ and $\eps/(1-\eps)$, so
\[
2\log\frac{1-\eps}{\eps}
=\log\frac{1-\eps}{\eps}-\log\frac{\eps}{1-\eps}
\ge\frac{(\log n)^2}{C_0}\bigl(p_{1-\eps}-p_\eps\bigr),
\]
that is,
\[
p_{1-\eps}-p_\eps\le\frac{2C_0}{(\log n)^2}\log\frac{1-\eps}{\eps}.
\]
Finally $4\eps(1-\eps)\le1$ gives $\log\frac{1-\eps}{\eps}
\le2\log\frac{1}{2\eps}$, hence
\[
p_{1-\eps}-p_\eps
\le\frac{4C_0}{(\log n)^2}\log\frac{1}{2\eps}
=\frac{2^{19}}{(\log n)^2}\log\frac{1}{2\eps},
\]
which is \eqref{eq:threshold}.
\end{proof}
\paragraph{The equivalent additive form.}
Friedgut and Kalai state the conjecture as an additive statement about a
single probability. Setting
\[
\delta=\frac{2^{19}}{(\log n)^2}\log\frac{1}{2\eps}
\]
recovers it. If $\mu(p)>\eps$ then $p>p_\eps$, so
Theorem~\ref{thm:threshold} gives $p+\delta>p_{1-\eps}$ and therefore
$\mu(p+\delta)>1-\eps$ whenever $p+\delta\le1$; when $p+\delta>1$ the
endpoint already has probability $1$. Conversely, if
$p_\eps+\delta<1$, apply this to any $p>p_\eps$ and let
$p\downarrow p_\eps$; continuity gives $\mu(p_\eps+\delta)\ge1-\eps$,
which is the same bound. When $p_\eps+\delta\ge1$ the bound is automatic.
\paragraph{The transition near its median.}
The log-odds estimate also describes the profiles of $\mu$ on both sides
of the median $p_*=p_{1/2}$, where the log-odds vanish. Integrating
\eqref{eq:differential} outward from $p_*$ 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}
\]
and the endpoint cases follow by continuity.
\clearpage
\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, 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. Preprint: \href{https://arxiv.org/abs/1911.10579v2}{arXiv:1911.10579v2}.
\bibitem{ExpectationEquivalence2026}
OpenAI,
\emph{Integral and fractional expectation thresholds are equivalent},
OpenAI Math Release preprint, 2026.
\bibitem{SecondKahnKalai2026}
OpenAI,
\emph{The second Kahn--Kalai conjecture},
OpenAI Math Release preprint, 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{document}