On iterated image size for point-symmetric relations
On iterated image size for point-symmetric relations
Yahya Ould Hamidoune∗
Abstract
Let Γ = (V,E) be a point-symmetric reflexive relation and let v ∈ V such that |Γ(v)|
is finite (and hence |Γ(x)| is finite for all x , by the transitive action of the group of
automorphisms). Let j ∈ N be an integer such that Γj(v)∩Γ−(v) = {v}. Our main result
states that
|Γj(v)| ≥ |Γj−1(v)|+ |Γ(v)| − 1.
As an application we have |Γj(v)| ≥ 1+(|Γ(v)|− 1)j. The last result confirms a recent
conjecture of Seymour in the case of vertex-symmetric graphs. Also it gives a short proof
for the validity of the Caccetta-Häggkvist conjecture for vertex-symmetric graphs and
generalizes an additive result of Shepherdson.
1 Introduction
Let G be an abelian group and let A,S be finite subsets of G with 0 /∈ S. Shepherdson’s
generalization of the Cauchy-Davenport Theorem states that |A ∪ (A + S)| ≥ |A| + |S| if
A ∪ (A+ S) contains no subgroup generated by some element of S.
As an application Shepherdson [14] proved that there are s1, · · · , sk ∈ S such that k ≤
⌉ and
1≤i≤k si = 0, if G is finite. The paper of Shepherdson includes thanks to Heilbronn
for suggesting this application together with a mention that Chowla obtained some related
zero-sum results.
Let D = (V,E) be a loopless finite digraph with minimal outdgree at least 1. It is well
known that D contains a directed cycle. The smallest cardinality of such a cycle is called the
girth of D and will be denoted by g(D). In 1970 Behzad, Chartrand and Wall [1] conjectured
that |V | ≥ r(g(D) − 1) + 1, if d+(x) = d−(x) = r for all x ∈ V . In 1978, Caccetta and
Häggkvist [3] made the stronger conjecture :
|V | ≥ min(d+x : x ∈ V )(g(D) − 1) + 1.
These conjectures are still largely open, even for the special case g(D) = 4. The reader
may find references and results about this question in [2].
These conjectures were proved by the author for vertex-symmetric digraphs [6]. This
result applied to Cayley graphs shows the validity of Shepherdson’s zero-sum result for all
finite groups. Unfortunately we were not aware at that moment of Shepherdson’s result. Our
Université Pierre et Marie Curie, Paris. yha@ccr.jussieu.fr
http://arxiv.org/abs/0704.0459v1
proof [6] is based on the properties of atoms of a finite digraph and Menger’s Theorem. A
description of Cayley graphs on finite Abelian groups such that |V | = r(g(D)− 1) + 1, where
r is the outdegree was obtained by the authors of [9] using Kemperman critical pair Theory
[12]. A new proof of the Caccetta and Häggkvist conjecture for vertex-symmetric digraphs
based on an additive result of Kemperman [11] and the representation of vertex symmetric
digraphs as coset graphs is given in [10].
More recently Seymour proposed the following conjecture [13]:
Let D be a loopless digraph and let r ≥ 1 be an integer. Then there is a vertex a such
|Γ(a) ∪ Γ2(a) ∪ · · · ∪ Γg−2(a)| ≥ r(g − 2),
where g = g(D).
The case g = 4 of this conjecture is mentioned in [2]. Seymour’s Conjecture implies
the conjecture of Behzad, Chartrand and Wall. Seymour’s Conjecture also implies that D
contains a directed cycle C with |C| ≤ ⌈
|V |−1
⌉ + 1. Notice that the Caccetta-Häggkvist
Conjecture states that D contains a directed cycle C with |C| ≤ ⌈
We shall allow infinite relations. The classical strong connectivity of digraphs needs to be
modified in this case in order to have a good lower bound of the size of the image of a set.
Also the presence of loops will simplify the presentation of the connectivity method. Since
this convention is unusual in this part of Graph Theory, we shall work with relations. Our
terminology will be developed in the next section.
Seymour’s conjecture may be formulated as follows :
Conjecture 1 [13] Let Γ = (V,E) be a finite reflexive relation and let j be an integer. Then
there is an x ∈ V such that one of the following conditions holds.
• |Γj(x)| ≥ 1 + j(|Γ(x)| − 1).
• Γ−1(x) ∩ Γj(x) 6= {x}.
Our main result is the following one:
Let Γ = (V,E) be a point-symmetric reflexive relation and let v ∈ V such that |Γ(v)| is
finite. Let j ≥ 1 be such that Γj(v) ∩ Γ−(v) = {v}. Then
|Γj(v)| ≥ |Γj−1(v)|+ |Γ(v)| − 1.
This result implies the validity of the above conjectures for vertex-symmetric graphs.
2 Terminology
Let V be a set. The diagonal of V is by definition ∆V = {(x, x) : x ∈ V }. Let E ⊂ V × V .
The ordered pair Γ = (V,E) will be called a relation . The relation Γ is said to be reflexive
if ∆V ⊂ E.
Let a ∈ V and let A ⊂ V . The image of a is by definition
Γ(a) = {x : (a, x) ∈ E}.
The image of A is by definition
Γ(A) =
Γ(x).
The cardinality of the image of x will be called the degree of x and will be denoted by d(x).
The relation Γ will be called regular with degree r if the elements of V have the same degree
r. We shall say that Γ is locally finite if d(x) is finite for all x. The reverse relation of Γ is
by definition Γ− = (V,E−), where E− = {(x, y)
(y, x) ∈ E}. The restriction of Γ = (V,E)
to a subset W ⊂ V is defined as the relation Γ[W ] = (W,E ∩ (W ×W )).
Let Φ = (W,F ) be a relation. A function f : V −→ W will be called a homomorphism if
for all x, y ∈ V such that (x, y) ∈ E, we have (f(x), f(y)) ∈ F .
The relation Γ will be called point-symmetric if for all x, y ∈ V , there is an automorphism
f such that y = f(x). Clearly a point-symmetric relation is regular.
We identify graphs and their relations. A loopless finite relation will be called a digraph.
The reader may replace everywhere the term ”relation” by ”graph”. In this case we mention
some differences between our terminology (which follows closely the standard notations of
Set Theory) and the notations used in some text books of Graph Theory. We point out that
our graphs are usually called directed graphs without multiple arcs or digraphs. Notice that
the notion Γ(a) used here and in Set Theory is written Γ+(a) in some text books in Graph
Theory. Also our notion of degree is called outdegree. We made the choice of Set Theory
terminology since some parts of this paper could have some interest in Group Theory and
Number Theory.
We shall use the composition Γ1◦· · ·◦Γk of relations Γ1, · · · ,Γk on V . If all these relations
are equal to Γ, we shall write
Γ1 ◦ · · · ◦ Γk = Γ
We shall write Γ0 for the identity relation IV = (V,∆V ). Also we shall write Γ
−j instead
of (Γ−)j .
3 Connectivity
Let Γ = (V,E) be a relation. For X ⊂ V , we shall write
∂Γ(X) = Γ(X) \X.
When the context is clear the reference to Γ will be omitted.
Let Γ = (V,E) be a locally finite reflexive relation. The connectivity of Γ is by definition
κ(Γ) = |V | − 1, if E = V × V. Otherwise
κ(Γ) = min{|∂(X)| : 1 ≤ |X| < ∞ and Γ(X) 6= V }. (1)
A subset X achieving the minimum in (1) is called a fragment of Γ. A fragment with
minimum cardinality is called an atom. The cardinality of an atom of Γ will be denoted by
a(Γ). It is not true that distinct atoms are always disjoint. But the author proved in [4] that,
if V is finite, then distinct atoms of Γ are disjoint, or distinct atoms of Γ− are disjoint. In
[7], it was observed that the same methods imply that distinct atoms of Γ are disjoint if V
is infinite. One may find in [8] unified proofs and some applications to Group Theory and
Additive Number Theory.
As a consequence of this result we could obtain :
Proposition 2 [4, 5, 7, 8] Let Γ = (V,E) be a locally-finite point-symmetric relation with
E 6= V × V . Suppose that V is infinite or that a(Γ) ≤ a(Γ−). Let A be an atom of Γ. Then
the subrelation Γ[A] induced on A is a point-symmetric relation. Moreover |A| ≤ κ(Γ).
4 Iterated image size
Lemma 3 Let Γ = (V,E) be a point-symmetric relation. Then for all i, Γi is point-symmetric.
Proof. Clearly any automorphism of Γ is an automorphism of Γi.
Theorem 4 Let Γ = (V,E) be a point-symmetric reflexive locally finite relation and let v ∈ V.
Let j ≥ 1 be an integer such that Γj(v) ∩ Γ−(v) = {v}. Then
|Γj(v)| ≥ |Γj−1(v)|+ |Γ(v)| − 1.
Proof.
Set V0 =
0≤i Γ
i(v). Clearly Γj(v) ⊂ V0. So we may assume that Γ = Γ[V0] and V = V0.
In the finite case this means that we restrict ourselves to the connected component con-
taining v.
We shall assume j > 1, since the result is obvious for j = 1.
With this hypothesis, clearly we have κ(Γ) ≥ 1.
Clearly
E 6= V × V.
Set κ = κ(Γ). Let A be an atom of Γ containing v. The proof is by induction on |Γ(v)|.
Put r = |Γ(v)|. Assume first
κ = r − 1.
Observe that Γj(v) 6= V . Then by the definition of κ, we have
|Γj(v) \ Γj−1(v)| = |∂(Γj−1(v))| ≥ κ = r − 1.
The result holds in this case. So we may assume
κ ≤ r − 2, (2)
and hence r ≥ 3. Then |A| ≥ 2, since otherwise κ = |∂(A)| = r − 1.
Case 1. V is infinite or a(Γ) ≤ a(Γ−).
By Proposition 2, Γ[A] is point-symmetric (and hence regular) and
|A| ≤ κ. (3)
Put r0 = |Γ(v) ∩A|.
Put X = Γj−1(v) and Y = A ∪X. By the induction hypothesis, we have
|∂(X) ∩A| = |Γj(v) ∩A| − |Γj−1(v) ∩A| ≥ r0 − 1. (4)
Let us prove that
∂(Y ) ⊂ (∂(X) \ A) ∪ (∂(A) \ Γ(v)). (5)
Since j ≥ 2, we have Γ(v) ⊂ X and hence Γ(v) ∩ ∂(X) = ∅. Then (5) clearly holds.
It follows that
∂(Y ) \ ∂(X) ⊂ ∂(A) \ Γ(v),
and hence we have
|∂(Y ) \ ∂(X)| ≤ |∂(A)| − |∂(A) ∩ Γ(v)|
= κ− |Γ(v)| + |A ∩ Γ(v)|
= κ+ r0 − r.
Hence
|∂(Y ) \ ∂(X)| ≤ κ+ r0 − r. (6)
Let us show that Γ(Y ) 6= V. This holds obviously if V is infinite. So we may assume V
finite. In this case we have |Γ−(v)| = |Γ(v)|.
Clearly we have
Γ(Y ) = Γ(X) ∪ (A \ Γ(v)) ∪ (∂(Y ) \ ∂(X)).
It follows using ( 3) and (6) that
|Γ(Y )| ≤ |Γ(X)|+ |A \ Γ(v)|+ |∂(Y ) \ ∂(X)|
≤ |V \ (Γ−(v) \ {v})| + |A| − r0 + κ+ r0 − r
= |V |+ |A|+ κ− 2r + 1
≤ |V |+ 2κ− 2r + 1 ≤ |V | − 3.
By the definition of κ, we have |∂(Y )| ≥ κ.
By (4) and (6),
|∂(X)| = |∂(X) ∩A|+ |∂(Y ) ∩ ∂(X)|
≥ r0 − 1 + |∂(Y )| − |∂(Y ) \ ∂(X)|
≥ r0 − 1 + κ− (κ+ r0 − r) = r − 1,
and the result is proved since
∂(X) = Γj(v) \ Γj−1(v).
Case 2. V is finite and a(Γ) > a(Γ−).
The argument used in Case 1, shows that |Γ−j(v) \ Γ−(j−1)(v)| ≥ r − 1.
By Lemma 3, Γj is point-symmetric. Since V is finite, Γj and its reverse Γ−j have the
same degree. Therefore observing that these relations are reflexive
r − 1 ≤ |Γ−j(v)| − |Γ−(j−1)(v)|
= |Γj(v)| − |Γ(j−1)(v)|.
The next result shows the validity of the conjecture of Seymour mentioned in the intro-
duction in the case of relations with a symmetric group of automorphisms.
Corollary 5 Let Γ = (V,E) be a point-symmetric reflexive relation with degree r and let
v ∈ V . Let j ≥ 1 be an integer such that Γj(v) ∩ Γ−(v) = {v} then
|Γj(v)| ≥ 1 + (r − 1)j.
Proof. The proof follows by induction using Theorem 4
Corollary 6 [6] Let Γ = (V,E) be a point-symmetric digraph with degree r ≥ 1 and put
g = g(Γ). Then |V | ≥ 1 + r(g − 1).
Proof. Set Φ = (V,E ∪ ∆V ). Let v ∈ V . Clearly we have Φ
g−2(v) ∩ Φ−(v) = {v}. By
Corollary 5, |V | − r = |V \ (Φ−(a) \ {a})| ≥ |Φg−2(v)| ≥ 1 + (g − 2)r.
This result, proved in [6], shows the validity of the Caccetta-Häggkvist Conjecture for
point-symmetric graphs. But the proof obtained here is much easier.
Corollary 7 [6] Let G be a group of order n and let S ⊂ G\{1} with cardinality = s. There
are elements s1, s2, · · · , sk ∈ S such that k ≤ ⌈
⌉ and
1≤i≤k
si = 1.
The proof follows by applying Corollary 6 to the Cayley graph defined by S on G. In
particular the theorem of Shepherdson mentioned in the introduction holds for all finite
groups.
References
[1] M. Behzad, G. Chartrand and C.E. Wall, On minimal regular digraphs with given girth,
Fund. Math. 69 (1970), 227-231.
[2] J. A. Bondy, Counting subgraphs: a new approach to the Caccetta-Häggkvist conjecture.
Graphs and combinatorics (Marseille, 1995). Discrete Math. 165/166 (1997), 71-80.
[3] L. Caccetta and R. Häggkvist, On minimal digraphs with given girth, Proceedings of
the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing
(Florida Atlantic Univ., Boca Raton, Fla., 1978), (Winnipeg, Man.), Congress. Numer.,
XXI, Utilitas Math. (1978), 181-187.
[4] Y.O. Hamidoune, Sur les atomes d’un graphe orienté, C.R. Acad. Sc. Paris A 284 (1977),
1253-1256.
[5] Y.O. Hamidoune, Quelques problèmes de connexité dans les graphes orientés, J. Comb.
Theory B 30 (1981), 1-10.
[6] Y.O. Hamidoune, An application of connectivity theory in graphs to factorizations of
elements in groups, Europ. J of Combinatorics 2 (1981), 349-355.
[7] Y.O. Hamidoune, Sur les atomes d’un graphe de Cayley infini, Discrete Math., 73 (1989),
297-300.
[8] Y.O. Hamidoune, On small subset product in a group. Structure Theory of set-addition,
Astérisque. no. 258(1999), xiv-xv, 281-308.
[9] Y.O. Hamidoune, A. Lladó and O. Serra, Vosperian and superconnected Abelian Cayley
digraphs, Graphs and Combinatorics 7(1991), 143-152.
[10] Melvyn B. Nathanson, The Caccetta-Häggkvist conjecture and Additive Number Theory,
http://arxiv.org/archive/math: eprint arXiv:math/0603469.
[11] J.H.B. Kempermann, On complexes in a semigroup, Nederl. Akad. Wetensch. Proc. Ser.
A. 59= Indag. Math. 18(1956), 247-254.
[12] J. H. B. Kemperman, On small sumsets in a Abelian group, Acta Math. 103 (1960),
63-88.
[13] P. Seymour, Oral communication.
[14] J. C. Shepherdson, On the addition of elements of a sequence, J. London Math Soc.
22(1947), 85-88.
http://arxiv.org/archive/math:
http://arxiv.org/abs/math/0603469
	Introduction
	Terminology 
	Connectivity
	Iterated image size
