The Setting
For an increasing graph property, the threshold width measures the change in edge density between two prescribed probabilities of membership. The relevant analytic bound concerns the distance between complementary levels of a function whose derivative dominates its value times one minus its value.
Let be a nonnegative integer and let be the labelled vertex set. A potential edge on is a two-element subset of , and is the set of potential edges.✦ A labelled graph on is an assignment of a Boolean value to each , with true meaning that the edge is present.✦ For labelled graphs and on , edge inclusion means that every edge present in is present in .✦
A Boolean graph property on a labelled vertex set is a Boolean-valued function of labelled graphs on . An increasing Boolean graph property on is a Boolean-valued function of labelled graphs on such that and imply .✦ A nontrivial Boolean graph property on is a Boolean-valued function of labelled graphs on such that some graph belongs to and some graph does not.✦ The real indicator of a Boolean value is when is true and when is false; means and variances of refer to this indicator.✦
For , let be the random graph in which edges are present independently with probability . The probability mass of a labelled graph is the product in (1): (1)✦ The graph probability is the probability that belongs to ✦, and is the expected squared deviation of its real indicator from its mean, as in (2): (2)
For , the edge influence is the probability that toggling changes , when every other edge is independently present with probability .✦ The total influence is the sum of these edge influences in (3): (3)✦
For a real level , the threshold quantile is the infimum of the biases in for which the graph probability is at least , as defined in (4): (4)✦ All logarithms are natural logarithms.
The Claim
Theorem 1. Let , and . Suppose that is continuous on , takes values strictly between and there, and is differentiable on . Suppose also that , , and for every . The logistic transition width satisfies (5): (5)✦
For , the logarithmic comparison is (6): (6)✦
Let be an increasing, nontrivial Boolean graph property on labelled vertices. Let and , and suppose that for every . Its quantile width satisfies (7): (7)✦
In the paper, the result reads: with and , the variance estimate implies on , and for integration of log odds between the and quantiles gives , with yielding Theorem 1.1.
What Is Checked
The statements concern real functions on closed intervals with the stated differential inequality, and increasing, nontrivial Boolean properties of labelled graphs with product edge measures and infimum quantiles.