On the size of spheres of relations with a transitive group of automorphisms

Abstract

Let $\Gamma =(V,E)$ be a point-transitive reflexive relation. Let $v\in V$ and put $r=|\Gamma (v)|.$ Also assume ${\Gamma }^j(v)\cap {\Gamma }^{-}(v)=\{v\}$. Then $$|{\Gamma }^j(v)\setminus {\Gamma }^{j-1}(v)|\ge r-1.$$ In particular we have $|{\Gamma }^j(v)|\ge 1+(r-1)j.$ The last result confirms a recent conjecture of Seymour in the case vertex-transitive graphs. Also it gives a short proof for the validity of the Caccetta-Häggkvist conjecture for vertex-transitive graphs and generalizes an additive result of Shepherdson.