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 be the number of vertices and let . A potential edge is a two-element subset of ; write for the set of potential edges.✦ A labelled graph is a configuration , with meaning that is present.✦ A Boolean graph property is a function , with value meaning membership. The real indicator of a Boolean value is for true and for false; the same symbol denotes its real indicator.✦
For a vertex permutation , the permuted edge is the image of ✦, and the relabelled graph assigns to an edge the value at its inverse image, as in (1).✦ (1) A Boolean graph property is vertex permutation invariant if for every vertex permutation and labelled graph .✦
Fourier Mass and Vertex Blocks
For , the Bernoulli mass of a bit is for and for .✦ On a finite coordinate set , the product probability weight of a configuration is the product in (2)✦; for , it is the random graph probability mass.✦ (2)
For an interior bias, put . The biased coordinate character is the normalized coordinate function✦, and the biased character indexed by is their product, as defined in (3).✦ At or , each coordinate character is zero. (3) The biased Fourier coefficient of a real-valued function is its product-measure expectation against , given by (4).✦ (4)
The pivotal edge influence is the probability that toggling changes , with all other edges independently present with probability .✦ The total influence is the sum in (5).✦ (5)
A vertex block is a subset of . An edge is incident with if at least one endpoint belongs to .✦ Write for all such edges and for the number of edges of incident with , as in (6). (6) For a finite ambient set , the uniform block probability is the probability obtained by choosing an -element subset of uniformly.✦ Write when .
For fixed and , define the block-selected mass , the low-degree mass , and the incident influence by (7), where is real. (7)
The Claim
Theorem 1. Let , , and , with natural logarithms. Put and . If is vertex permutation invariant, then (8)✦
For the same , let be any Boolean graph property satisfying for every block of size . Then (9)✦
More generally, let , let be integers, and let and be real with . Suppose every nonempty with satisfies , and every block of size satisfies . Then (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.