The Setting
Let be a set of labelled vertices. The potential edges form the set in (1); a labelled graph is a function in the same display, with indicating that the edge is present. (1) A Boolean graph property is a function , with indicating that belongs to the property.
For labelled graphs and , edge inclusion means that every edge present in is present in .✦ An increasing graph property is a Boolean graph property such that and imply .✦ A nontrivial graph property is a Boolean graph property that takes both values and .✦
A permutation of acts on edges and labelled graphs by (2). (2) A vertex-invariant graph property is a Boolean graph property satisfying for every permutation of and every labelled graph .✦ For a permutation of and a potential edge , the permuted edge is the image of under . For a permutation of and a labelled graph , the relabelled graph assigns to each potential edge the value that assigns to .
The random graph , where , has each potential edge present independently with probability . The probability mass of the random graph at a labelled graph is the probability of obtaining . The Boolean indicator is the real number when and otherwise.✦ The graph property probability is the expectation in (3). (3)✦
The infimum quantile at a real level is the infimum in (4), taken over edge densities in the closed unit interval. (4)✦
All logarithms are natural logarithms.
The Claim
Theorem 1. Let , and let be a nontrivial increasing graph property on vertices that is invariant under vertex permutations. For , its quantile width satisfies (5): (5)✦
What Is Checked
The claim is stated over nontrivial increasing vertex-invariant Boolean properties of labelled graphs and their infimum quantiles (4).