OctoInformBeta

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

Lemma 3.3: An influence bound for invariant graph properties when log⁡n≥16\log n\ge16

Vertex blocks bound 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

A vertex block selects Fourier coefficients according to how many of their edges meet it. The quantity of interest is the mass on nonempty edge sets of bounded size, measured against the total pivotal influence.

Let nn be the number of vertices and let Vn={0,…,n−1}V_n=\{0,\ldots,n-1\}. A potential edge is a two-element subset of VnV_n; write En=(Vn2)E_n=\binom{V_n}{2} for the set of potential edges.✦ A labelled graph is a configuration x∈{0,1}Enx\in\{0,1\}^{E_n}, with xe=1x_e=1 meaning that ee is present.✦ A Boolean graph property is a function f:{0,1}En→{0,1}f:\{0,1\}^{E_n}\to\{0,1\}, with value 11 meaning membership. The real indicator of a Boolean value is 11 for true and 00 for false; the same symbol ff denotes its real indicator.✦

For a vertex permutation π\pi, the permuted edge πe\pi e is the image of ee✦, and the relabelled graph πx\pi x assigns to an edge the value at its inverse image, as in (1).✦ πe={π(v):v∈e},(πx)e=xπ−1e.\pi e=\{\pi(v):v\in e\},\qquad (\pi x)_e=x_{\pi^{-1}e}.(1) A Boolean graph property ff is vertex permutation invariant if f(πx)=f(x)f(\pi x)=f(x) for every vertex permutation π\pi and labelled graph xx.✦

Fourier Mass and Vertex Blocks

For 0≤p≤10\le p\le1, the Bernoulli mass wp(b)w_p(b) of a bit bb is pp for b=1b=1 and 1−p1-p for b=0b=0.✦ On a finite coordinate set AA, the product probability weight Wp(x)W_p(x) of a configuration x∈{0,1}Ax\in\{0,1\}^A is the product in (2)✦; for A=EnA=E_n, it is the random graph probability mass.✦ Wp(x)=∏i∈Awp(xi).W_p(x)=\prod_{i\in A}w_p(x_i).(2)

For an interior bias, put σ=p(1−p)\sigma=\sqrt{p(1-p)}. The biased coordinate character χi\chi_i is the normalized coordinate function✦, and the biased character χS\chi_S indexed by S⊆AS\subseteq A is their product, as defined in (3).✦ At p=0p=0 or p=1p=1, each coordinate character is zero. χi(x)=xi−pσ(0<p<1),χS(x)=∏i∈Sχi(x).\chi_i(x)=\frac{x_i-p}{\sigma}\quad(0<p<1),\qquad \chi_S(x)=\prod_{i\in S}\chi_i(x).(3) The biased Fourier coefficient gˆ(S)\widehat g(S) of a real-valued function g:{0,1}A→ℝg:\{0,1\}^A\to\mathbb R is its product-measure expectation against χS\chi_S, given by (4).✦ gˆ(S)=𝔼p[g(x)χS(x)]=∑x∈{0,1}AWp(x)g(x)χS(x).\widehat g(S)=\mathbb E_p[g(x)\chi_S(x)] =\sum_{x\in\{0,1\}^A}W_p(x)g(x)\chi_S(x).(4)

The pivotal edge influence Ie,p(f)I_{e,p}(f) is the probability that toggling ee changes ff, with all other edges independently present with probability pp.✦ The total influence Ip(f)I_p(f) is the sum in (5).✦ Ip(f)=∑e∈EnIe,p(f).I_p(f)=\sum_{e\in E_n}I_{e,p}(f).(5)

A vertex block BB is a subset of VnV_n. An edge is incident with BB if at least one endpoint belongs to BB.✦ Write FBF_B for all such edges and rB(S)r_B(S) for the number of edges of SS incident with BB, as in (6). FB={e∈En:e∩B≠⌀},rB(S)=|S∩FB|.F_B=\{e\in E_n:e\cap B\ne\varnothing\},\qquad r_B(S)=|S\cap F_B|.(6) For a finite ambient set UU, the uniform block probability ℙU,m\mathbb P_{U,m} is the probability obtained by choosing an mm-element subset of UU uniformly.✦ Write ℙm\mathbb P_m when U=VnU=V_n.

For fixed ff and pp, define the block-selected mass Ck(B)C_k(B), the low-degree mass Lk(f)L_k(f), and the incident influence Jp(B;f)J_p(B;f) by (7), where kk is real. Ck(B)=∑S⊆En1≤rB(S)≤kfˆ(S)2,Lk(f)=∑S⊆En0<|S|≤k2/2fˆ(S)2,Jp(B;f)=∑e∈FBIe,p(f).\begin{aligned} C_k(B)&=\sum_{\substack{S\subseteq E_n\\1\le r_B(S)\le k}} \widehat f(S)^2,\qquad L_k(f)=\sum_{\substack{S\subseteq E_n\\0<|S|\le k^2/2}} \widehat f(S)^2,\\ J_p(B;f)&=\sum_{e\in F_B}I_{e,p}(f). \end{aligned}(7)

The Claim

Theorem 1. Let n≥2n\ge2, log⁡n≥16\log n\ge16, and 0<p<10<p<1, with natural logarithms. Put m=⌊n⌋m=\lfloor\sqrt n\rfloor and k=σlog⁡m/64k=\sigma\log m/64. If ff is vertex permutation invariant, then Lk(f)≤4m−1/4Ip(f).L_k(f)\le4m^{-1/4}I_p(f).(8)✦

For the same n,p,m,kn,p,m,k, let ff be any Boolean graph property satisfying Ck(B)≤m−1/4Jp(B;f)C_k(B)\le m^{-1/4}J_p(B;f) for every block BB of size mm. Then Lk(f)≤4m−1/4Ip(f).L_k(f)\le4m^{-1/4}I_p(f).(9)✦

More generally, let 0≤p≤10\le p\le1, let 1≤m≤n1\le m\le n be integers, and let kk and aa be real with a≥0a\ge0. Suppose every nonempty S⊆EnS\subseteq E_n with |S|≤k2/2|S|\le k^2/2 satisfies ℙm(1≤rB(S)≤k)≥m/(2n)\mathbb P_m(1\le r_B(S)\le k)\ge m/(2n), and every block BB of size mm satisfies Ck(B)≤aJp(B;f)C_k(B)\le aJ_p(B;f). Then Lk(f)≤4aIp(f).L_k(f)\le4aI_p(f).(10)✦

What Is Checked

The claims (8), (9) and (10) are stated over Boolean properties of finite labelled graph cubes with product Bernoulli weights, under their respective hypotheses of vertex permutation invariance, bounds on the mass selected by each block, or capture by uniformly chosen blocks together with such mass bounds.