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 be the labelled vertex set and let be its potential edges.✦ A labelled graph is a configuration , with when is present.✦ A vertex permutation sends an edge to and relabels configurations as in (1); a graph function is vertex-invariant when the second equality holds for every and : (1)
Identify Boolean values with their real indicators and .✦ For a finite coordinate set and , the Bernoulli mass and product probability mass are given by (2); when , is the random graph probability mass: (2) The pivotal influence of coordinate on a Boolean function is the probability that toggling changes .✦ The total influence of a Boolean function is the sum of its coordinate influences, as in (3), where denotes the configuration obtained by toggling coordinate ; for graph functions the coordinate influence is the edge influence : (3)
For , put . For a real function on , the biased coordinate characters for , product characters for , and Fourier coefficients are defined by (4), where expectation uses : (4)
An edge touches a vertex block when it has an endpoint in .✦ The free coordinate set of a vertex block is the set of edges with at least one endpoint in , as in (5): (5) For a coordinate set , a value set , and , the gluing of and is the function that agrees with on and with elsewhere. For a coordinate set , value sets and , a subset , a function , and exterior values , the restriction is the function given by (6): (6) The block restriction of a graph function is the Boolean function on the edges in obtained by fixing the edges wholly outside to the exterior configuration .
For a finite set and , let be the set of -element subsets of . For a finite set , an integer , and an event on , the uniform block probability is the probability of when is chosen uniformly from , as in (7): (7)✦
The Claim
Theorem 1. Let be vertex-invariant, let have size , and let . Put . The fixed-block low-degree bound is (8): (8)✦ For any bias , every exterior configuration and every satisfy the conditional influence bound (9): (9)✦
Let be finite sets, with real weights , and choose subsets and for each . Suppose , , and , and let be real. Under the block and incidence hypotheses (10), the weighted averaging bound is (11): (10) (11)✦
Let be a finite set, let have two elements, and let . For a uniform , the edge-touch bound is (12): (12)✦
In the paper, the result reads as the bound (13) for , a vertex-invariant , , , an integer , a uniform -element block , , and : (13)
What Is Checked
The statements concern vertex-invariant Boolean graph functions on the finite cube and their restrictions to , together with finite weighted families for (11) and uniform fixed-cardinality subsets of a finite vertex set for (12).