The Setting
Let be a finite simple graph on a vertex set , and let be a nonnegative integer. Let be the complete graph on vertices. The containment problem asks for the probability that the graph obtained by retaining each edge of independently with probability contains an ordinary copy of .
For a finite ground set , a real parameter and a subset , the Bernoulli weight is the product (1)✦ For a finite ground set , a real parameter and a function , the Bernoulli expectation is the weighted sum of with the weights in (1): (2)✦ The Bernoulli probability of an event , for a finite ground set and a real parameter , is the sum of the Bernoulli weights of the subsets in , where is when and otherwise: (3)✦ For , let be the distribution on subsets of obtained by including each element independently with probability ; (2) and (3) are expectation and probability under .
Write . The edge set of consists of the unordered pairs of distinct vertices: (4)✦ For a subset of the edge set (4), the graph is the simple graph with vertex set and edge set : (5)✦ The product random graph is the graph in (5) when has distribution on subsets of .
For finite simple graphs and , let be the number of ordinary unlabelled non-induced subgraphs of isomorphic to , counting their vertex sets and any isolated vertices. Write for the number of unordered edges of .✦
For a finite simple graph , the expected copy count in is the Bernoulli expectation (2) of : (6)✦ For a finite simple graph , the containment probability in is the Bernoulli probability (3) that contains at least one ordinary copy of : (7)✦
The Claim
Definition 1 (Graph thresholds). The critical threshold is the infimum of the parameters in at which the containment probability (7) reaches the budget one-half: (8)✦ For a finite simple graph and a nonnegative integer , the expectation threshold is the infimum of the parameters in at which the expected copy count (6) reaches the budget one-half for every actual subgraph of , with its own vertex set: (9)✦
Theorem 1 (Attainment and positivity). Let be a finite simple graph with , and take the thresholds in (8) and (9). Then (10)✦ (11)✦ If , then (12)✦
What Is Checked
The statements (10) and (11) concern finite simple target graphs with and independent edge subsets of , with the additional hypothesis in (12).