The Setting
Let be a digraph on a finite vertex set , with arcs written , and let be a natural number. The -fold blow-up of is the digraph on the vertex set , where , with an arc whenever (1)✦
The lemma asks which properties of pass to , and how a set of vertices of grows in one and in two steps along arcs, compared with the set of its first coordinates in . The library states eight facts: three properties of , four facts on how sets of vertices of grow along arcs, and an inequality between the sizes of three finite sets.
Images and Conditions on Digraphs
The image of a set of vertices of a digraph is the set of vertices that receive an arc from a vertex of : (2)✦ The set can meet . The map is the composition of the image map with itself. Where both graphs are in play, and are the images in and in .
A digraph is oriented when it has no loop and no pair of opposite arcs and ✦, and has positive indegree when every vertex has an in-neighbor, a vertex with .✦
A set of vertices of a digraph on is proper when . A digraph satisfies the subset deficit when every nonempty proper set of its vertices has (3)✦ and has strict growth when every nonempty proper set of its vertices has (4)✦
The Claim
Theorem 1. Let be a digraph on a finite vertex set , let be a natural number, and let be the -fold blow-up of . If is oriented, then (5)✦ If has positive indegree, then (6)✦ If is oriented, has positive indegree, satisfies the subset deficit and has fewer than vertices, then (7)✦ For every set of vertices of , with the set of first coordinates of its vertices, (8)✦ (9)✦ (10)✦ and if has positive indegree and , then (11)✦ For finite subsets , and of any set, if , then (12)✦
In the paper, the result reads: if is an oriented graph on vertices, all of positive indegree, that satisfies the subset deficit, and is an integer, then the digraph obtained by replacing each vertex by a transitive tournament on vertices and each arc by all arcs from the block at to the block at is oriented, has all indegrees positive, and satisfies for every nonempty proper set of its vertices.
What Is Checked
The claim is stated over a digraph on a finite vertex set and its -fold blow-up , the images and , and four conditions on a digraph: being oriented, positive indegree, the subset deficit and strict growth.