The Setting
A variance estimate in terms of pivotal edge influences compares the fluctuations of a Boolean graph function with its sensitivity to individual edges. The spectral input here is a bound on the Fourier mass of small, nonempty sets of edges.
The set of potential edges consists of the two-element subsets of the labelled vertices.✦ A labelled graph is a configuration , with when is present.✦ A Boolean value is identified with its real indicator, equal to for true and for false.✦
For a finite coordinate set and , the Bernoulli mass of a bit and the product probability mass of a configuration are defined by (1) For , the weight in (1) is the random graph probability mass.✦ Write and for expectation and probability under these weights. For a Boolean graph function , its graph property probability is its expectation, and its variance is its mean squared deviation from that expectation, as in (2): (2) For , let denote with the bit at toggled. For a Boolean graph function and an edge , the pivotal edge influence is the probability that toggling the bit at changes , with all other edges chosen independently at bias .✦ The total influence of a Boolean graph function is the sum of its pivotal edge influences, as in (3): (3) Set . For a finite coordinate set , an index and a subset , the biased coordinate character and the product character are the functions on given by (4) For a real function on and a subset , the biased Fourier coefficient is the expectation of the product of and , as in (5): (5) For graph functions, in (5) uses and the real indicator of .
Captured Fourier Mass
A real coefficient family on a finite set is an assignment of a real number to each subset . For a real coefficient family on a finite set and positive parameters , the captured squared mass is the sum of the squared coefficients over the nonempty subsets of below the degree cutoff in (6): (6) All logarithms are natural.
The Claim
Theorem 1. Let be a Boolean function of labelled graphs on vertices, and let . With , the variance Parseval identity is (7): (7)✦ The Dirichlet influence identity is (8): (8)✦
More generally, let be a real coefficient family on a finite set . Let , , , and satisfy the spectral identities in (9): (9) Suppose satisfies and the capture bound (10), with as in (6): (10) Then the variance bound from capture is (11): (11)✦
Alternatively, suppose and, whenever , there exists satisfying and (10). Under (9), the variance bound at all scales is (12): (12)✦
In the paper, the result reads: for and its choices of and the Fourier cutoff parameter , Parseval, captured mass, and give , while for , Poincaré gives , which suffices for the same final constant.
What Is Checked
The graph identities concern arbitrary Boolean functions on labelled graphs at interior biases; the numerical estimates concern arbitrary real coefficient families on a finite coordinate set satisfying (9) and the respective capture hypotheses.