The Setting
Let a finite group act on a ground set . For a finite subset , its copy orbit is the set of distinct images under this action✦, and its orbit count is the number of these images, as in (1): (1) An unlabelled copy of is a member of .✦
A finite probability law on a finite set is a real weight function with nonnegative values summing to one.✦ For a finite probability law on a finite set , the probability of an event is .✦ A finite probability law on a finite set has full support if every weight is positive.✦ On a nonempty , the uniform law assigns weight to each outcome.✦
The uniform copy law of a finite subset is the uniform law on .✦ The copy containment probability of the uniform copy law of a finite subset , for a finite , is the event probability in (2): (2)✦
Probability Trees
A probability tree on of depth is a finite rooted tree whose leaves all have depth , with a full-support probability law on the outgoing branches at each node and a finite subset of labelling each arc.✦ A tree of depth zero is a leaf. A full path of a probability tree is a complete history of branch choices from the root to a leaf; the leaf has one empty history.✦ The path union of a full path in a probability tree is the union of the arc labels along , as in (3): (3)✦ A probability tree on is disjoint if the labels on each full path are pairwise disjoint.✦
Level capacities of a probability tree on of depth are natural numbers bounding the cardinality of every arc label at the corresponding level.✦ Levels are numbered from one; the declarations index these levels from zero. For a real parameter , at a node with branch set , branch weights and labels , the label distribution is -spread if (4) holds for every finite : (4) A probability tree on of depth has level spread parameters if every outgoing label distribution at level is -spread.✦
Predecessors and Extensions
A real score on subsets of a finite set has a maximizing subset✦; write for a chosen subset attaining its maximum over all subsets of .✦ For a finite subset and a real parameter , the predecessor score is the real function on finite subsets of given in (5), and the maximizing predecessor is a chosen subset of maximizing this score over all subsets of .✦ (5)
For nested finite sets and an initial copy , the copy extension tree is the probability tree of depth that at level chooses a copy under the uniform copy law conditioned on containing , labels the arc by , and continues from .✦
The Claim
Theorem 1. Let be finite and nonempty, and let . Suppose for every nonempty . There exist an integer , a probability tree on of depth and capacities satisfying (6): (6)✦
In the paper, the result reads: for a graph with at least one edge and at most vertices, with expectation threshold at budget one-half and , there is a disjoint probability tree on whose path unions are copies of with its isolated vertices removed, every level is -spread, and its label sizes satisfy , for , and .
What Is Checked
The tree assertion is stated over a finite group action, a finite nonempty subset and a positive satisfying the orbit count hypothesis.
For a nonempty finite and satisfying for every nonempty , the maximizing predecessor satisfies (7): (7)✦
Let be finite and . For a copy and a finite disjoint from , the conditional containment bound is (8): (8)✦
Every full path of the copy extension tree for and satisfies (9): (9)✦