The Setting
For a graph event, the choice of vertex labels and the effect of adding edges are separate issues. Both enter the hypotheses of the main threshold statement.
The Definition
Definition 1. Let be a nonnegative integer and write . The edge set of the complete graph on is the family of unordered vertex pairs in (1): (1)✦ A labelled graph on is a Boolean edge configuration, an element of the space in (2); the value means that the edge is present: (2)✦
A graph is a subgraph of , written , when the edge inclusion condition (3) holds: (3)✦
For a vertex permutation and an edge , the permuted edge is the image in (4): (4)✦ The relabelled graph of is the configuration defined by (5): (5)✦
A Boolean membership function , with indicating membership, is invariant under vertex permutations when it satisfies (6): (6)✦ An increasing graph property is a Boolean function whose accepted configurations are closed under edge inclusion, as in (7): (7)✦ A nontrivial graph property is a Boolean function with both an accepted and a rejected configuration, as in (8): (8)✦
In the paper, the result reads: for , is the family of two-element subsets of , a graph is a point of , a graph property is a family invariant under all vertex permutations, increasing means that adding edges preserves membership, and nontrivial means that the family is neither empty nor the whole configuration space.
What Is Checked
The definitions range over every nonnegative integer and Boolean functions on , using the edge order (3) and the vertex relabelling (5).