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

Original · EN

Let Γ=(V,E) be a point-transitive reflexive relation. Let v∈ V and put r=|Γ(v)|. Also assume Γʲ(v)∩ Γ⁻(v)={v}. Then |Γʲ (v) Γʲ⁻¹ (v)| ≥ r-1. In particular we have |Γʲ (v)| ≥ 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.