The Setting
Let be the number of labelled vertices, and write . A potential edge on is a two-element subset of ✦; a labelled graph on is an assignment of an edge indicator to each potential edge , with indicating presence.✦ The edge set and graph space are (1) A Boolean graph function specifies a property of the graphs in (1), with indicating membership. The Boolean indicator sends to the real number and to the real number ; expectations use these real values.✦
For a vertex permutation , the permuted edge is the image of under ✦, and the relabelled graph is given by (2) A vertex-invariant Boolean graph function is a function whose value is preserved by every vertex relabelling in (2): (3)✦
Fix an edge bias . The random graph probability mass of a labelled graph is the product of the probabilities of its edge indicators: (4)✦ The distribution in (4) is denoted by . For a Boolean graph function , the graph property probability is the probability that under ✦, and the graph variance is the expected squared deviation of its Boolean indicator from its mean: (5)
For a graph , an edge , and an indicator , let be the graph obtained from by setting its edge indicator at to . The pivotal edge influence of a Boolean graph function at an edge is the probability that changing edge changes , with every other edge present independently with probability .✦ The total influence of a Boolean graph function is the sum of its pivotal edge influences over all edges : (6) All logarithms are natural logarithms.
The Claim
Theorem 1. Let be an integer, let be vertex-invariant in the sense of (3), and let . For the variance in (5) and total influence in (6), the uniform variance influence bound is (7): (7)✦ The pointwise variance bound is the specialization of (7) to fixed , and . For fixed , vertex-invariant , and : (8)✦
What Is Checked
Both bounds are stated over Boolean functions on the labelled graphs in (1), with vertex permutation invariance, and , using the independent edge probability mass in (4) and the variance and pivotal edge influences in (5) and (6).