The Setting
Let be a digraph on a finite vertex set , with arcs written . An oriented graph is a digraph with no loop and no pair of opposite arcs and .✦ A digraph on has positive indegree when every vertex has an in-neighbor, a vertex with .✦
The image of a set of vertices of is the set of vertices that receive an arc from a vertex of , (1)✦ and . The image may meet itself.
A set of vertices is proper when . A digraph on has strict growth when every nonempty proper set of vertices satisfies (2)✦
The question is whether a nonempty finite oriented graph with positive indegree can have strict growth. The library takes it up under one further hypothesis on the arcs of , the pruning statement, which concerns finite families of pairs of vertices and the conflicts between them.
Conflicts and Pruning
Let be a relation on a finite set . A pair in conflicts with a pair in when and .✦ Two finite families and of pairs in are conflict-free when no pair of conflicts with a pair of .✦
The point sets and of two finite families and of pairs in are the sets of the points and of their conflicts, (3)
The left image of a finite family of pairs in is the set of pairs obtained by advancing the first coordinate of a pair of along an arc✦, and the right image of a finite family is the set obtained by advancing the second, (4)✦ A pair in is covered by and when it lies in .✦ For two further finite families and , the uncovered part of is the set of the points of that and do not cover.✦
A pruning result for finite families and of pairs in consists of two finite families and that are conflict-free, that keep every pair of conflicting with no pair of and every pair of with which no pair of conflicts, and that satisfy (5)✦ The pruning statement for is the assertion that any two finite families and of pairs in have a pruning result.✦
The Claim
Theorem 1. Let be an oriented graph with positive indegree on a nonempty finite vertex set , and suppose the pruning statement holds for the arcs of , as a relation on . Then some nonempty proper set of vertices of satisfies (6)✦
In the paper, the result reads: there is no nonempty finite oriented graph in which every vertex has an in-neighbor and every nonempty proper set of vertices satisfies .
What Is Checked
The claim is stated over oriented graphs with positive indegree on a nonempty finite vertex set, the image of (1) and strict growth (2), and the pruning statement with what it is built from: conflicts and conflict-free families, the point sets and , the images and , covered pairs, the uncovered part of and pruning results.