The Setting
For a finite graph , consider the event that a random graph on vertices contains an ordinary, non-induced copy of . The question is how its containment and expectation constraints relate to the distinct edge sets obtained by permuting vertices.
Write and let be the complete graph on . An edge of is an unordered pair of distinct vertices; write for the set of these edges.✦ For , the graph is the simple graph on all of with edge set , including vertices incident to no edge.✦ The edge count is the number of unordered edges of .✦
For finite simple graphs and , let be the number of ordinary unlabelled non-induced subgraphs of isomorphic to , including their vertex sets and any isolated vertices. An actual subgraph of is a graph specified by a vertex subset of and an edge subset of whose endpoints lie in that vertex subset.
For , let be the set of endpoints of edges in . The incident-vertex subgraph of has vertex set and edge set .✦ The incident-vertex graph is the simple graph on with the adjacency of .✦
Copies and Their Laws
Let a finite group act on a finite set . The orbit of distinct copies of is the family in (1); an unlabelled copy of is a member of this family. The copy count is the number of members of , and the internal copy count for is the number of members of contained in : (1) For the action of all permutations of on , abbreviate these notations to , and .
A finite probability law on a finite set is a function assigning nonnegative weights to outcomes , with .✦ The probability of an event is .✦ The uniform law on a nonempty finite set is the probability law that assigns weight to every outcome.✦
The uniform copy law of is the uniform probability law on .✦ The copy containment probability , for , is the probability under this law that a copy contains , as defined in (2): (2)✦
For a finite ground set and a real parameter , the Bernoulli subset weight of and the Bernoulli expectation of a real-valued function on subsets of are defined by (3): (3) For , the law includes each coordinate independently with probability ; then and .
For a finite simple graph , the expected unlabelled copy count is the Bernoulli expectation in (4): (4)✦ For , write for drawn from on .
The Claim
Theorem 1. Let a finite group act on a finite set , let , and let . Then (5)✦ For every nonnegative integer and every , (6)✦ For every real and every , (7)✦ Let be a finite simple graph with , and let . Suppose that for every actual subgraph of . There is an edge set satisfying (8)✦
What Is Checked
The ratio (5) is stated for finite group actions, the identities (6) and (7) for edge sets under vertex permutations of , and the transfer (8) for finite graphs on at most vertices with expectation constraints on every actual subgraph.