The Setting
A threshold quantile locates a prescribed probability level as the edge bias varies.
Let be the number of labelled vertices, and let be the set of their two-element subsets, the potential edges.✦ A labelled graph on labelled vertices is a function , with meaning that is present.✦ Edge inclusion means that every edge present in is present in .✦
An increasing graph property on labelled graphs is a Boolean function such that and imply .✦ A nontrivial graph property is a Boolean function for which some graph belongs to the property and some graph does not.✦ The real indicator of a Boolean value is for false and for true; in real expressions, denotes this indicator.✦
For a real parameter , the graph weight of a labelled graph is the finite product in (1), and the graph mean of a Boolean graph property is the finite weighted sum there: (1) For , is the probability mass of when every potential edge is present independently with probability , and is the probability that the random graph belongs to .
Write for the graph obtained from by toggling . For , the edge influence of an edge on a Boolean graph property is the probability that toggling changes , with all other edges independently present with probability .✦ The finite expression in (2) defines this influence for real ; the total influence of a Boolean graph property is the sum of its edge influences over potential edges: (2)
For a real level , the threshold quantile of a Boolean graph property is the infimum of the biases in at which the graph probability is at least , as in (3): (3)✦
The Claim
Theorem 1. Let be an increasing graph property on labelled vertices. The Russo-Margulis formula (4) holds for every real : (4)✦ Suppose also that is nontrivial. For every , the quantile identity (5) holds: (5)✦ For , the quantile has the location given by (6): (6)✦
In the paper, the result reads: for increasing Boolean , satisfies ; for a nontrivial increasing property, , and for ; the variance estimate gives a positive interior derivative, and every has an attained interior quantile with .
What Is Checked
The statements concern Boolean functions on the finite set of labelled graphs, with increasingness defined by edge inclusion and nontriviality requiring both a member and a nonmember.