The Setting
The comparison concerns the appearance of a fixed finite simple graph in a product random graph on vertices. Write for its number of vertices and for its number of unordered edges.
For a nonnegative integer , let . The edges of the complete graph on form the set in (1): (1)✦ For , the graph is the simple graph on with edge set .✦ For finite simple graphs and , let be the number of ordinary unlabelled non-induced subgraphs of isomorphic to , counting the vertex sets and any isolated vertices.
The product measure on subsets of a finite ground set , for , includes each coordinate independently with probability . For a real parameter and a subset of a finite ground set , the Bernoulli subset weight is the product with a factor for each coordinate in and a factor for each coordinate outside .✦ For , this is the mass in (2): (2)✦ Let denote the power set of . For a real parameter and a function , the Bernoulli expectation is the sum of the Bernoulli subset weights multiplied by over all subsets of .✦ For , this expectation and the probability of an event are the sums in (3): (3) The random graph is for sampled from .
For a nonnegative integer , a real parameter and a finite simple graph , the expected copy count is the Bernoulli expectation at of over subsets of .✦ For , it is the expected number of ordinary unlabelled non-induced subgraphs of isomorphic to , including their vertex sets and any isolated vertices✦; the containment probability is the probability that contains a subgraph isomorphic to a finite simple graph , as in (4): (4) The critical threshold is the infimum in (5) of the parameters whose containment probability is at least one-half: (5)✦ The expectation threshold is the infimum in (6) of the parameters for which every actual subgraph of has expected copy count at least one-half: (6)✦
The Bound Conditions
The base-two logarithm is denoted by , as in (7), and : (7)✦ The threshold bound condition is the conjunction of the two inequalities in (8): (8)✦ The universal threshold statement is the assertion in (9): (9)✦
The Claim
Theorem 1. Let be an integer and let be a finite simple graph with at most vertices and at least one edge. The threshold bound condition is satisfied, as asserted in (10): (10)✦
The universal threshold statement asserts these bounds for every integer and every finite simple graph with and : (11)✦
What Is Checked
The statement ranges over finite simple graphs on at most vertices, with and , and uses the product measure on the unordered pairs of distinct vertices of and the ordinary subgraph counts .