OctoInformBeta

OpenAI preprint, September 2026 · §3. Restricting to the edges incident with a vertex block

Proposition 3.2: Conditional influence and weighted averaging for vertex-invariant graph functions

Block restrictions control low-degree Fourier mass.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Restricting a graph function to the edges incident with a vertex block leaves a Boolean function on those edges. The quantities here are its pivotal influences and the Fourier mass of the original function with a small, nonzero number of coordinates incident with the block.

Let [n][n] be the labelled vertex set and let En=([n]2)E_n=\binom{[n]}2 be its potential edges.✦ A labelled graph is a configuration x∈{0,1}Enx\in\{0,1\}^{E_n}, with xe=1x_e=1 when ee is present.✦ A vertex permutation π\pi sends an edge ee to π(e)={π(v):v∈e}\pi(e)=\{\pi(v):v\in e\} and relabels configurations as in (1); a graph function f:{0,1}En→{0,1}f:\{0,1\}^{E_n}\to\{0,1\} is vertex-invariant when the second equality holds for every π\pi and xx: (πx)e=xπ−1(e),f(πx)=f(x).(\pi x)_e=x_{\pi^{-1}(e)},\qquad f(\pi x)=f(x).(1)

Identify Boolean values with their real indicators 00 and 11.✦ For a finite coordinate set AA and 0≤p≤10\le p\le1, the Bernoulli mass qpq_p and product probability mass wpw_p are given by (2); when A=EnA=E_n, wpw_p is the random graph probability mass: qp(b)={p,b=1,1−p,b=0,wp(x)=∏i∈Aqp(xi).q_p(b)=\begin{cases}p,&b=1,\\1-p,&b=0,\end{cases} \qquad w_p(x)=\prod_{i\in A}q_p(x_i).(2) The pivotal influence Ii,p(g)I_{i,p}(g) of coordinate ii on a Boolean function g:{0,1}A→{0,1}g:\{0,1\}^A\to\{0,1\} is the probability that toggling ii changes gg.✦ The total influence Ip(g)I_p(g) of a Boolean function g:{0,1}A→{0,1}g:\{0,1\}^A\to\{0,1\} is the sum of its coordinate influences, as in (3), where x⊕ix^{\oplus i} denotes the configuration obtained by toggling coordinate ii; for graph functions the coordinate influence is the edge influence Ie,p(f)I_{e,p}(f): Ii,p(g)=Prp{g(x)≠g(x⊕i)},Ip(g)=∑i∈AIi,p(g).I_{i,p}(g)=\Pr_p\{g(x)\ne g(x^{\oplus i})\},\qquad I_p(g)=\sum_{i\in A}I_{i,p}(g).(3)

For 0<p<10<p<1, put σ=p(1−p)\sigma=\sqrt{p(1-p)}. For a real function gg on {0,1}A\{0,1\}^A, the biased coordinate characters χi\chi_i for i∈Ai\in A, product characters χS\chi_S for S⊆AS\subseteq A, and Fourier coefficients gˆ(S)\widehat g(S) are defined by (4), where expectation uses wpw_p: χi(x)=xi−pσ,χS(x)=∏i∈Sχi(x),gˆ(S)=𝔼p[g(x)χS(x)].\chi_i(x)=\frac{x_i-p}{\sigma},\qquad \chi_S(x)=\prod_{i\in S}\chi_i(x),\qquad \widehat g(S)=\mathbb E_p[g(x)\chi_S(x)].(4)

An edge e∈Ene\in E_n touches a vertex block B⊆[n]B\subseteq[n] when it has an endpoint in BB.✦ The free coordinate set FB⊆EnF_B\subseteq E_n of a vertex block B⊆[n]B\subseteq[n] is the set of edges with at least one endpoint in BB, as in (5): FB={e∈En:e∩B≠⌀}.F_B=\{e\in E_n:e\cap B\ne\varnothing\}.(5) For a coordinate set AA, a value set VV, and F⊆AF\subseteq A, the gluing x⊔Fy∈VAx\sqcup_F y\in V^A of x∈VFx\in V^F and y∈VA\Fy\in V^{A\setminus F} is the function that agrees with xx on FF and with yy elsewhere. For a coordinate set AA, value sets VV and WW, a subset F⊆AF\subseteq A, a function g:VA→Wg:V^A\to W, and exterior values y∈VA\Fy\in V^{A\setminus F}, the restriction gy:VF→Wg_y:V^F\to W is the function given by (6): (x⊔Fy)i={xi,i∈F,yi,i∉F,gy(x)=g(x⊔Fy).(x\sqcup_F y)_i=\begin{cases}x_i,&i\in F,\\y_i,&i\notin F,\end{cases} \qquad g_y(x)=g(x\sqcup_F y).(6) The block restriction fB,yf_{B,y} of a graph function ff is the Boolean function on the edges in FBF_B obtained by fixing the edges wholly outside BB to the exterior configuration yy.

For a finite set UU and 0≤m≤|U|0\le m\le|U|, let ℬm(U)\mathcal B_m(U) be the set of mm-element subsets of UU. For a finite set UU, an integer 0≤m≤|U|0\le m\le|U|, and an event PP on ℬm(U)\mathcal B_m(U), the uniform block probability Pr⁡B{P(B)}\Pr_B\{P(B)\} is the probability of PP when BB is chosen uniformly from ℬm(U)\mathcal B_m(U), as in (7): PrB{P(B)}=|{B∈ℬm(U):P(B)}|(|U|m).\Pr_B\{P(B)\}= \frac{|\{B\in\mathcal B_m(U):P(B)\}|}{\binom{|U|}{m}}.(7)✦

The Claim

Theorem 1. Let f:{0,1}En→{0,1}f:\{0,1\}^{E_n}\to\{0,1\} be vertex-invariant, let B⊆[n]B\subseteq[n] have size m≥3m\ge3, and let 0<p<10<p<1. Put k=σlog⁡m/64k=\sigma\log m/64. The fixed-block low-degree bound is (8): ∑S⊆En1≤|S∩FB|≤kfˆ(S)2≤m−1/4∑e∈FBIe,p(f).\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,p}(f).(8)✦ For any bias 0≤p≤10\le p\le1, every exterior configuration y∈{0,1}En\FBy\in\{0,1\}^{E_n\setminus F_B} and every e∈FBe\in F_B satisfy the conditional influence bound (9): Ie,p(fB,y)≤1m∑d∈FBId,p(fB,y).I_{e,p}(f_{B,y})\le \frac1m\sum_{d\in F_B}I_{d,p}(f_{B,y}).(9)✦

Let ℬ,𝒮,ℐ\mathcal B,\mathcal S,\mathcal I be finite sets, with real weights μb,ws,Ji\mu_b,w_s,J_i, and choose subsets Pb⊆𝒮P_b\subseteq\mathcal S and Tb⊆ℐT_b\subseteq\mathcal I for each b∈ℬb\in\mathcal B. Suppose μb≥0\mu_b\ge0, Ji≥0J_i\ge0, and a≥0a\ge0, and let dd be real. Under the block and incidence hypotheses (10), the weighted averaging bound is (11): ∑s∈Pbws≤a∑i∈TbJi(b∈ℬ),∑b∈ℬi∈Tbμb≤d(i∈ℐ).\sum_{s\in P_b}w_s\le a\sum_{i\in T_b}J_i \quad(b\in\mathcal B),\qquad \sum_{\substack{b\in\mathcal B\\i\in T_b}}\mu_b\le d \quad(i\in\mathcal I).(10) ∑b∈ℬμb∑s∈Pbws≤ad∑i∈ℐJi.\sum_{b\in\mathcal B}\mu_b\sum_{s\in P_b}w_s \le a d\sum_{i\in\mathcal I}J_i.(11)✦

Let UU be a finite set, let e⊆Ue\subseteq U have two elements, and let 1≤m≤|U|1\le m\le|U|. For a uniform B∈ℬm(U)B\in\mathcal B_m(U), the edge-touch bound is (12): PrB{B∩e≠⌀}≤2m|U|.\Pr_B\{B\cap e\ne\varnothing\}\le\frac{2m}{|U|}.(12)✦

In the paper, the result reads as the bound (13) for n≥2n\ge2, a vertex-invariant f:{0,1}En→{0,1}f:\{0,1\}^{E_n}\to\{0,1\}, 0<p<10<p<1, σ=p(1−p)\sigma=\sqrt{p(1-p)}, an integer 3≤m≤n3\le m\le n, a uniform mm-element block B⊆[n]B\subseteq[n], k=σlog⁡m/64k=\sigma\log m/64, and FB={e∈En:e∩B≠⌀}F_B=\{e\in E_n:e\cap B\ne\varnothing\}: ∑S⊆EnPrB{1≤|S∩FB|≤k}fˆ(S)2≤2mnm−1/4Ip(f).\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_p(f).(13)

What Is Checked

The statements concern vertex-invariant Boolean graph functions on the finite cube {0,1}En\{0,1\}^{E_n} and their restrictions to FBF_B, together with finite weighted families for (11) and uniform fixed-cardinality subsets of a finite vertex set for (12).