The paper addresses a recent conjecture of Seymour concerning the size of the union of iterated neighborhoods of vertices in digraphs (in relation to the girth of the digraph). The conjecture is shown to be true for vertex-transitive digraphs.
Specifically, the author shows the following: If \(\Gamma\) is a point-symmetric reflexive locally finite relation, \(v\) is a point of \(\Gamma\), and \(\Gamma^j(v) \cap \Gamma^-(v) = \{ v \} \), then \[ | \Gamma^j(v)| \geq | \Gamma^{j-1}(v)| + | \Gamma^1(v)| - 1 , \] (or, using the graph-theoretical language, if \(\Gamma\) is a vertex-transitive digraph and \(v\) is a vertex of \(\Gamma\) that does not lie on a oriented cycle of length smaller than or equal to \(j+1\), then the set of vertices of \(\Gamma\) whose distance from \(v\) is smaller than or equal to \(j\) must be large). Consequently, \[ | \Gamma^j(v)| \geq 1 + (| \Gamma^1(v)| -1) \cdot j . \]
The proof relies on several of author’s previous results concerning the connectivity of vertex-transitive graphs and on induction on the out-degree of \(v\). The result is also shown to (re)prove the veracity of the Caccetta-Häggkvist conjecture for the case of vertex-transitive graphs and a related Shepherdson result for Cayley graphs.