The Setting
A graph property on a fixed vertex set is a Boolean function of its possible edges.
Let be the number of vertices and let be the set of two-element subsets of .✦ A labelled graph configuration assigns a presence indicator to every potential edge .✦ For a graph property , write when belongs to . The real indicator of a Boolean value is the real number that is at false and at true, and these are the values used in real expressions involving .✦
For a graph configuration , an edge , and , the modified configuration is the configuration that agrees with off and has value at .
The Definition
Definition 1. Let , let be a graph property, and let . The graph weight of a configuration is the product in (1): (1)✦ The graph mean of a graph property at a real parameter is the weighted sum in (2): (2)✦ For a real threshold and a graph property , the infimum quantile is the infimum in (3): (3)✦ The variance of a graph property at a real parameter is the weighted centered second moment in (4): (4)✦ For a real parameter , a graph property , and an edge , the pivotal edge influence is the weighted disagreement in (5): (5)✦ The total influence of a graph property at a real parameter is the sum in (6): (6)✦
In the paper, the result reads: under independent Bernoulli- edges, is the probability of the property ; for , ; for Boolean , is the probability over coordinates other than that , and is the sum of these influences over edges; variance is the second centered moment.
What Is Checked
These definitions are stated over labelled graph configurations on vertices, Boolean graph properties, and individual potential edges, with real parameters and .