The Setting
Take a finite oriented graph, a tournament say, and a vertex of it. Some vertices are out-neighbors of ; others are reached from by a directed path of length two and by no arc. Must some vertex have at least as many vertices of the second kind as of the first? Seymour’s second-neighborhood conjecture says that it must.
The library states the conjecture for every oriented graph on a nonempty finite vertex set, beside two statements: a reduction of a counterexample to an oriented graph of a special kind on a grid of vertices, and a pruning theorem on deleting pairs from two families of pairs of points under a relation.
Neighborhoods and Growth
A digraph on a finite vertex set , written with arrows for its arcs, is oriented when it has no loop and no pair of opposite arcs and .✦ The first neighborhood of a vertex of is the set of its out-neighbors✦, and its second neighborhood is the set of the vertices at directed distance exactly two from : (1)✦
The image of a set of vertices of is the set of the vertices, in or not, that receive an arc from a vertex of , and : (2)✦ A digraph on has positive indegree when every vertex has an in-neighbor, a vertex with ✦, and strict growth when every nonempty proper subset satisfies (3)✦
Conflicting Pairs
Let be a relation on a set , and call the elements of pairs. A pair conflicts with a pair when and .✦ Two finite families and of pairs are conflict-free when no pair of conflicts with a pair of .✦ For finite families and , the set collects the points ✦ and the set the points of the conflicts between and : (4)✦
The left image and the right image of a finite family of pairs advance the first, respectively the second, coordinate along an arc: (5) A pair is covered by finite families and when it lies in .✦ For two further finite families and , the uncovered part of is the set of the points of that are not covered by and .✦
The Claim
Theorem 1 (Seymour’s second-neighborhood conjecture). Let be an oriented graph on a nonempty finite vertex set . Then has a good vertex, a vertex with (6)✦
Theorem 2 (Counterexample reduction). Let be an oriented graph on a nonempty finite vertex set that is a counterexample to Seymour’s conjecture, one with no good vertex. Then there are a positive integer and an oriented graph with positive indegree and strict growth on the vertex set (7)✦
Theorem 3 (Pruning theorem). Let be a relation on a set . Then satisfies the pruning statement: any two finite families and of pairs admit a pruning result, conflict-free subfamilies and that keep every pair of or in no conflict between and and satisfy (8)✦ where is the uncovered part of for and .
What Is Checked
The three theorems are stated over oriented graphs on a nonempty finite vertex set, with the first and second neighborhoods of their vertices and good vertices; over counterexamples to Seymour’s conjecture, positive indegree, the image of a vertex set and strict growth; and over a relation on a set, with conflicting pairs, conflict-free families, the sets and , the left and right images, covered pairs, the uncovered part of , pruning results and the pruning statement.