Prove
Lemma 1. Let m≥2 be real and let h: 0,1 ^J→0,1 satisfy I_i(h)≤I(h)/m for every…Lemma 2 ([Exact averaging over a restriction]). Let F⊆E_n , put H=E_n F , and,…Proposition
Fix B , and fix an arbitrary assignment y to H_B=E_n F_B . The free set F_B contains 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 m2 edges within B and, for each fixed w∈[n] B , the m edges u,w :u∈B . Every orbit has size at least m , since m≥3 . 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)(f_y)m (e∈F_B). Lemma 1 applies separately to every y . Its right-hand side is linear in I(f_y) , so averaging and using Lemma 2 ([Exact averaging over a restriction]) gives ∑_ S⊆E_n; 1≤|S∩F_B|≤k f(S)^2 ≤m^ -1/4 ∑_ e∈F_B I_e(f). Finally average over B . Each endpoint of a fixed edge belongs to B with probability m/n , whence _B(e∈F_B)≤2m/n . This proves .