CONNECTIVITY OF ADDITION CAYLEY GRAPHS

DAVID GRYNKIEWICZ, VSEVOLOD F. LEV, AND ORIOL SERRA

Abstract. For any finite abelian group G and any subset S ⊆ G, we determine the connectivity of the addition Cayley graph induced by S on G. Moreover, we show that if this graph is not complete, then it possesses a minimum vertex cut of a special, explicitly described form.

1. Background: addition Cayley graphs

For a subset S of the abelian group G, we denote by Cay_{G}^{+}(S) the addition Cayley graph induced by S on G; recall that this is the undirected graph with the vertex set G and the edge set {(g_{1}, g_{2}) ∈ G × G: g_{1} + g_{2} ∈ S}. Note that S is not assumed to be symmetric, and that if S is finite, then Cay_{G}^{+}(S) is regular of degree |S| (if one considers each loop to contribute 1 to the degree of the corresponding vertex).

The twins of the usual Cayley graphs, addition Cayley graphs (also called sum graphs) received much less attention in the literature; indeed, [A] (independence number), [CGW03] and [L] (hamiltonicity), [C92] (expander properties), and [Gr05] (clique number) is a nearly complete list of papers, known to us, where addition Cayley graphs are addressed. To some extent, this situation may be explained by the fact that addition Cayley graphs are rather difficult to study. For instance, it is well-known and easy to prove that any connected Cayley graph on a finite abelian group with at least three elements is hamiltonian, see [Mr83]; however, apart from the results of [CGW03], nothing seems to be known on hamiltonicity of addition Cayley graphs on finite abelian groups. Similarly, the connectivity of a Cayley graph on a finite abelian group is easy to determine, while determining the connectivity of an addition Cayley graph is a non-trivial problem, to the solution of which the present paper is devoted. The reader will see that investigating this problem leads to studying rather involved combinatorial properties of the underlying group.

2. Preliminaries and summary of results

Let Γ be a graph on the finite set V. The (vertex) connectivity of Γ, denoted by κ(Γ), is the smallest number of vertices which are to be removed from V so that

The first author is supported in part by the National Science Foundation, as an MPS-DRF postdoctoral fellow, under grant DMS-0502193.

2 DAVID GRYNKIEWICZ, VSEVOLOD F. LEV, AND ORIOL SERRA

the resulting graph is either disconnected or has only one vertex. Clearly, if Γ is complete, then κ(Γ) = |V | − 1, while otherwise we have κ(Γ) ≤ |V | − 2, and κ(Γ) can be alternatively defined as the size of a minimum vertex cut of Γ. (A complete graph does not have vertex cuts.) Evidently, vertex cuts and connectivity of a graph are not affected by adding or removing loops.

Our goal is to determine the connectivity of the addition Cayley graphs, induced on finite abelian groups by their subsets, and accordingly we use additive notation for the group operation. In particular, for subsets A and B of an abelian group, we write

A ± B := {a ± b: a ∈ A, b ∈ B},

which is abbreviated by A ± b in the case where B = {b} is a singleton subset.

For the rest of this section, we assume that S is a subset of the finite abelian group G.

It is immediate from the definition that, for a subset A ⊆ G, the neighborhood of A in Cay_{G}^{+}(S) is the set S −A, and it is easy to derive that Cay_{G}^{+}(S) is complete if and only if either S = G, or S = G\{0} and G is an elementary abelian 2-group (possibly of zero rank). Furthermore, it is not difficult to see that Cay_{G}^{+}(S) is connected if and only if S is not contained in a coset of a proper subgroup of G, with the possible exception of the non-zero coset of a subgroup of index 2; this is [L, Proposition 1]. Also, since Cay_{G}^{+}(S) is |S|-regular, we have the trivial bound κ(Cay_{G}^{+}(S)) ≤ |S|.

If H is a subgroup of G and g is an element of G with 2g ∈ S + H, then g + H ⊆ S − (g + H); consequently, the boundary of g + H in Cay_{G}^{+}(S) has size

|(S − (g + H)) \ (g + H)| = |S + H| − |H|.

Assuming in addition that S+H ≠ G, we obtain (S−(g+H))∪(g+H) = S+H −g ≠ G, implying κ(Cay_{G}^{+}(S)) ≤ |S + H| − |H|. Set

2 ∗ G := {2g: g ∈ G},

so that the existence of g ∈ G with 2g ∈ S + H is equivalent to the condition (S + 2 ∗ G) ∩ H ≠ ∅. Motivated by the above observation, we define

H_{G}(S) := {H ≤ G: (S + 2 ∗ G) ∩ H ≠ ∅, S + H ≠ G}

and let

η_{G}(S) := min{|S + H| − |H|: H ∈ H_{G}(S)}.

In the latter definition and throughout, we assume that the minimum of an empty set is infinite, and we allow comparison between infinity and real numbers according to the “naıve” rule. Thus, for instance, we have κ(Cay_{G}^{+}(S)) ≤ η_{G}(S) even if H_{G}(S) is vacuous.

CONNECTIVITY OF ADDITION CAYLEY GRAPHS 3

Another important family of sets with small boundary is obtained as follows. Suppose that the subgroups L ≤ G_{0} ≤ G and the element g_{0} ∈ G_{0} satisfy

(i) |G_{0}/L| is even and larger than 2; (ii) S + L = (G \ G_{0}) ∪ (g_{0} + L).

Fix g ∈ G_{0} \ L with 2g ∈ L and consider the set A := (g + L) ∪ (g + g_{0} + L). The neighborhood of this set in Cay_{G}^{+}(S) is

S − A = (G \ G_{0}) ∪ (g + L) ∪ (g + g_{0} + L) = (G \ G_{0}) ∪ A,

whence (S − A) ∪ A ≠ G and |(S − A) \ A| = |G \ G_{0}| = |S + L| − |L|. Consequently, κ(Cay_{G}^{+}(S)) ≤ |S + L| − |L|. With this construction in mind, we define L_{G}(S) to be the family of all those subgroups L ≤ G for which a subgroup G_{0} ≤ G, lying above L, and an element g_{0} ∈ G_{0} can be found so that properties (i) and (ii) hold, and we let

λ_{G}(S) := min{|S + L| − |L|: L ∈ L_{G}(S)}.

Thus, κ(Cay_{G}^{+}(S)) ≤ λ_{G}(S).

Our first principal result is the following.

Theorem 1. If S is a proper subset of the finite abelian group G, then

κ(Cay_{G}^{+}(S)) = min{η_{G}(S), λ_{G}(S), |S|}.

Let Γ be a graph on the vertex set V. We say that the non-empty subset V_{0} ⊂ V is a fragment of Γ if the neighborhood N(V_{0}) of V_{0} satisfies |N(V_{0}) \ V_{0}| = κ(Γ) and N(V_{0}) ∪ V_{0} ≠ V; that is, the boundary of V_{0} is a minimum vertex-cut, separating V_{0} from the (non-empty) remainder of the graph. Notice that if Γ is not complete, then it has fragments; for instance, if Γ′ is obtained from Γ by removing a minimum vertex cut, then the set of vertices of any connected component of Γ′ is a fragment of Γ.

As the discussion above shows, if κ(Cay_{G}^{+}(S)) = η_{G}(S), then Cay_{G}^{+}(S) has a fragment which is a coset of a subgroup H ∈ H_{G}(S) with |S +H|−|H| = η_{G}(S); similarly, if κ(Cay_{G}^{+}(S)) = λ_{G}(S), then Cay_{G}^{+}(S) has a fragment which is a union of at most two cosets of a subgroup L ∈ L_{G}(S) with |S + L| − |L| = λ_{G}(S).

The reader will easily verify that Theorem 1 is an immediate corollary of Theorem 2 below. The latter shows that the minimum in the statement of Theorem 1 is attained, with just one exception, on either η_{G}(S) or |S|. Being much subtler, Theorem 2 is also more technical, and to state it we have to bring into consideration a special subfamily of L_{G}(S). Specifically, let L_{G}^{∗}(S) be the family of those subgroups L ≤ G such that for some G_{0} ≤ G, lying above L, and some g_{0} ∈ G_{0}, the following conditions hold:

(L1) G_{0}/L is a cyclic 2-group of order |G_{0}/L| ≥ 4, and ⟨g_{0}⟩ + L = G_{0};

4 DAVID GRYNKIEWICZ, VSEVOLOD F. LEV, AND ORIOL SERRA

(L2) G/G_{0} is an elementary abelian 2-group (possibly of zero rank);

(L3) exp(G/L) = exp(G_{0}/L);

(L4) S + L = (G \ G_{0}) ∪ (g_{0} + L) and S ∩ (g_{0} + L) is not contained in a proper

coset of L. A little meditation shows that L_{G}^{∗}(S) ⊆ L_{G}(S) and that conditions (L1)–(L3) imply

G/L ≅ (G_{0}/L) ⊕ (ℤ/2ℤ)^{r} ≅ (ℤ/2^{k}ℤ) ⊕ (ℤ/2ℤ)^{r},

for some k ≥ 2 and r ≥ 0. Notice also that if L, G_{0}, and g_{0} are as in (L1)–(L4), and G_{0} = G, then L is a subgroup of G of index at least 4, and S is contained in an L-coset, whence Cay_{G}^{+}(S) is disconnected.

Theorem 2. Let S be a proper subset of the finite abelian group G. There exists at most one subgroup L ∈ L_{G}^{∗}(S) with |S + L| − |L| ≤ |S| − 1. Moreover,

(i) if L is such a subgroup, then κ(Cay_{G}^{+}(S)) = λ_{G}(S) = |S + L| − |L| and η_{G}(S) ≥ |S|;

(ii) if such a subgroup does not exist, then κ(Cay_{G}^{+}(S)) = min{η_{G}(S), |S|}.

Postponing the proof to Section 4, we now list some of the consequences.

Corollary 1. Let S be a proper subset of the finite abelian group G such that Cay_{G}^{+}(S) is connected. If either |S| ≤ |G|/2 or G does not contain a subgroup isomorphic to (ℤ/4ℤ) ⊕ (ℤ/2ℤ), then κ(Cay_{G}^{+}(S)) = min{η_{G}(S), |S|}.

Proof. If κ(Cay_{G}^{+}(S)) ≠ min{η_{G}(S), |S|}, then by Theorem 2 there exists L ∈ L_{G}^{∗}(S) with |S + L| − |L| ≤ |S| − 1. Choose L ≤ G_{0} ≤ G and g_{0} ∈ G_{0} satisfying (L1)–(L4). Since Cay_{G}^{+}(S) is connected, the subgroup G_{0} is proper. Consequently,

|S| ≥ |S + L| − |L| + 1 = |G| − |G_{0}| + 1 > \frac{1}{2} |G|,

and it also follows that G/L contains a subgroup isomorphic to (ℤ/4ℤ) ⊕ (ℤ/2ℤ), which implies that G itself contains such a subgroup. □

Our next result shows that under the extra assumption κ(Cay_{G}^{+}(S)) < |S|, the conclusion of Theorem 1 can be greatly simplified.

Theorem 3. Let S be a proper subset of the finite abelian group G. If κ(Cay_{G}^{+}(S)) < |S|, then

κ(Cay_{G}^{+}(S)) = min{|S + H| − |H|: H ≤ G, S + H ≠ G}.

Theorem 3 will be derived from Theorem 2 in Section 4. Note that the assumption κ(Cay_{G}^{+}(S)) < |S| of Theorem 3 cannot be dropped: say, if S is the non-zero coset of a subgroup H ≤ G of index 2, then Cay_{G}^{+}(S) is a complete bipartite graph of

CONNECTIVITY OF ADDITION CAYLEY GRAPHS 5

connectivity |G|/2, while |S + H| − |H| = 0 and S + H ≠ G. We also notice that, despite its simple and neat conclusion (and one which mirrors the corresponding result for usual Cayley graphs), Theorem 3 gives no way to determine whether κ(Cay_{G}^{+}(S)) < |S| holds, and hence no way to find the connectivity unless it is known to be smaller than |S| a priori. Of course, a necessary and sufficient condition for κ(Cay_{G}^{+}(S)) < |S| to hold follows readily from Theorem 2.

Corollary 2. If S is a proper subset of the finite abelian group G, then in order for κ(Cay_{G}^{+}(S)) < |S| to hold it is necessary and sufficient that there is a subgroup K ∈ H_{G}(S) ∪ L_{G}^{∗}(S) with |S + K| ≤ |S| + |K| − 1.

Observe that if g is an element of G with 2g ∈ S, then g is a neighbor of itself in Cay_{G}^{+}(S); consequently, the boundary of {g} contains |S| − 1 elements so that κ(Cay_{G}^{+}(S)) < |S|. Hence Theorem 3 implies the following corollary.

Corollary 3. Let S be a proper subset of the finite abelian group G. If S∩(2∗G) ≠ ∅, and in particular if G has odd order and S is non-empty, then

κ(Cay_{G}^{+}(S)) = min{|S + H| − |H|: H ≤ G, S + H ≠ G}.

We conclude this section with two potentially useful lower-bound estimates for κ(Cay_{G}^{+}(S)).

Corollary 4. Let S be a proper subset of the finite abelian group G. If Cay_{G}^{+}(S) is connected, then in fact

κ(Cay_{G}^{+}(S)) ≥ \frac{1}{2} |S|.

Corollary 4 follows from Theorem 3 and the observation that if |S + H| − |H| = κ(Cay_{G}^{+}(S)) > 0 for a subgroup H ≤ G, then S intersects at least two cosets of H, so that |S + H| ≥ 2|H|, and therefore |S + H| − |H| ≥ \frac{1}{2} |S + H| ≥ \frac{1}{2} |S|.

Corollary 5. Let S be a proper subset of the finite, non-trivial abelian group G, and let p denote the smallest order of a non-zero subgroup of G. If Cay_{G}^{+}(S) is connected, then in fact

κ(Cay_{G}^{+}(S)) ≥ min{|S| − 1, p}.

The proof is similar to that of the previous corollary: if κ(Cay_{G}^{+}(S)) < |S|−1, then by Theorem 3 there exists a subgroup H ≤ G with |S + H| − |H| = κ(Cay_{G}^{+}(S)) > 0; this subgroup is non-zero and hence |S + H| − |H| ≥ |H| ≥ p.

6 DAVID GRYNKIEWICZ, VSEVOLOD F. LEV, AND ORIOL SERRA

3. Auxiliary results

In this section, we gather the tools needed for the proof of Theorems 2 and 3. This includes a simple consequence from [Gk01] or [Gk02] (rephrased), a classical theorem of Kneser on periodicity of sumsets, a result from [L05], which is a ‘dual’ version of a well-known structure theorem of Kemperman [Km60], and three original lemmas.

Given a subgroup H of the abelian group G, by φ_{H} we denote the canonical homomorphism from G onto G/H. Though the notation φ_{H} does not specify the underlying group G, it is always implicit from the context and no confusion will arise.

For a subset S of the abelian group G, the (maximal) period of S will be denoted by π(S); recall that this is the subgroup of G defined by

π(S) := {g ∈ G: S + g = S},

and that S is called periodic if π(S) ≠ {0} and aperiodic otherwise. Thus, S is a union of π(S)-cosets, and π(S) lies above any subgroup H ≤ G such that S is a union of H-cosets. Observe also that π(S) = G if and only if either S = ∅ or S = G, and that φ_{π(G)}(S) is an aperiodic subset of the group G/π(S).

Proposition A (Grynkiewicz, [Gk01, (c.5)]; see also [Gk02, Proposition 5.2]). Let A be a finite, non-empty subset of an abelian group. If |π(A \ {a})| > 2 for some a ∈ A, then |π(A \ {a′})| = 1 for every group element a′ ≠ a.

Theorem A (Kneser, [Kn53, Kn55]; see also [Mn76]). Let A and B be finite, nonempty subsets of an abelian group G. If

|A + B| ≤ |A| + |B| − 1,

then, letting H := π(A + B), we have

|A + B| = |A + H| + |B + H| − |H|.

We now turn to the (somewhat involved) statement of [L05, Theorem 2]; the reader can consult the source for the explanations and comments.

By an arithmetic progression in the abelian group G with difference d ∈ G, we mean a set of the form {g + d, g + 2d, …, g + kd}, where g is an element of G and k is a positive integer. Thus, cosets of finite cyclic subgroups (and in particular, singleton sets) are considered arithmetic progressions, while the empty set is not. For finite subsets A and B of an abelian group and a group element c, we write

ν_{c}(A, B) := |{(a, b) ∈ A × B: c = a + b}|;

that is, ν_{c}(A, B) is the number of representations of c as a sum of an element of A and an element of B. Observe that ν_{c}(A, B) > 0 if and only if c ∈ A + B. The smallest number of representations of an element of A + B will be denoted by μ(A, B):

μ(A, B) := min{ν_{c}(A, B): c ∈ A + B}.

Following Kemperman [Km60], we say that the pair (A, B) of finite subsets of the abelian group G is elementary if at least one of the following conditions holds:

(I) min{|A|, |B|} = 1; (II) A and B are arithmetic progressions sharing a common difference, the order

of which in G is at least |A| + |B| − 1; (III) A = g_{1} + (H_{1} ∪ {0}) and B = g_{2} − (H_{2} ∪ {0}), where g_{1}, g_{2} ∈ G, and where

H_{1} and H_{2} are non-empty subsets of a subgroup H ≤ G such that H = H_{1} ∪ H_{2} ∪ {0} is a partition of H; moreover, c := g_{1} + g_{2} is the only element of A + B with ν_{c}(A, B) = 1;

(IV) A = g_{1} + H_{1} and B = g_{2} − H_{2}, where g_{1}, g_{2} ∈ G, and where H_{1} and H_{2} are non-empty, aperiodic subsets of a subgroup H ≤ G such that H = H_{1} ∪ H_{2} is a partition of H; moreover, μ(A, B) ≥ 2.

We say that the pair (A, B) of subsets of an abelian group satisfies Kemperman’s condition if either A + B is aperiodic or μ(A, B) = 1 holds.

Theorem B (Lev, [L05, Theorem 2]). Let A and B be finite, non-empty subsets of the abelian group G. A necessary and sufficient condition for (A, B) to satisfy both

|A + B| ≤ |A| + |B| − 1

and Kemperman’s condition is that there exist non-empty subsets A_{0} ⊆ A and B_{0} ⊆ B and a finite, proper subgroup F < G such that

(i) each of A_{0} and B_{0} is contained in an F -coset, |A_{0} + B_{0}| = |A_{0}| + |B_{0}| − 1, and the pair (A_{0}, B_{0}) satisfies Kemperman’s condition;

(ii) each of A \ A_{0} and B \ B_{0} is a (possibly empty) union of F -cosets; (iii) the pair (φ_{F} (A), φ_{F} (B)) is elementary; moreover, either F is trivial, or φ_{F} (A_{0})+

φ_{F} (B_{0}) has a unique representation as a sum of an element of φ_{F} (A) and an element of φ_{F} (B).

Lemma 1. Let L ≤ G_{0} ≤ G be finite abelian groups. If G_{0}/L is a cyclic 2-group and 2 ∗ (G/L) is a proper subgroup of G_{0}/L, then exp(G_{0}/L) = exp(G/L).

Proof. Write |G_{0}/L| = 2^{k} so that k is a positive integer. Since |2 ∗ (G/L)| is a proper divisor of 2^{k}, we have 2^{k−1}g = 0 for every g ∈ 2 ∗ (G/L). Equivalently, 2^{k}g ∈ L for every g ∈ G, whence exp(G/L) ≤ 2^{k} = exp(G_{0}/L). The inverse estimate exp(G_{0}/L) ≤ exp(G/L) is trivial. □

The following lemma is similar in flavor to a lemma used by Kneser to prove Theorem A; cf. [Kn55, Km60].

Lemma 2. Suppose that S is a finite subset, and that H and L are finite subgroups of the abelian group G satisfying |L| ≤ |H| and S + H ≠ S + H + L. Let I := H ∩ L. If

max{|S + H| − |H|, |S + L| − |L|} ≤ |S + I| − |I|,

then in fact

|S + H| − |H| = |S + L| − |L| = |S + I| − |I|;

moreover, there exists g ∈ G such that (S + I) \ (g + H + L) is a (possibly empty) union of (H + L)-cosets, and one of the following holds:

(i) (S + I) ∩ (g + H + L) = g + I; (ii) (S + I) ∩ (g + H + L) = (g + H + L) \ (g + (H ∪ L)) and |H| = |L|.

Proof. Factoring by I, we assume without loss of generality that I = {0}. Since S + H ≠ S + H + L, there exists s_{0} ∈ S with s_{0} + L ⊈ S + H, and we let S_{0} := S∩(s_{0}+H +L). It is instructive to visualize the coset s_{0}+H +L as the grid formed by |L| horizontal lines (corresponding to the H-cosets contained in s_{0} + H + L) and |H| vertical lines (corresponding to the L-cosets contained in s_{0}+H +L). The intersection points of these two families of lines correspond to the elements of s_{0} + H + L, and the condition s_{0} + L ⊈ S + H implies that there is a horizontal line free of elements of S.

Let h := φ_{L}(S_{0}) (the number of vertical lines that intersect S_{0}) and l := φ_{H}(S_{0}) (the number of horizontal lines that intersect S_{0}); thus, 1 ≤ h ≤ |H| and 1 ≤ l < |L|. We also have, in view of the hypotheses,

(|H| − h)l ≤ |(S_{0} + H) \ S_{0}| ≤ |(S + H) \ S| ≤ |H| − 1,  (1)

whence

(|H| − h)(l − 1) ≤ h − 1,  (2)

and similarly,

(|L| − l)(h − 1) ≤ l − 1.  (3)

To begin with, suppose that l = 1, and hence h = 1 by (3). In this case, |S_{0}| = 1, whence S ∩ (s_{0} + H + L) = {s_{0}}. Furthermore, (1) yields (S_{0} + H) \ S_{0} = (S + H) \ S, and likewise we have (S_{0} + L) \ S_{0} = (S + L) \ S. This shows that

|S + H| − |S| = |H| − 1, |S + L| − |S| = |L| − 1,  (4)

and S \ S_{0} is a union of (H + L)-cosets, thus establishing the assertion (with g = s_{0}) in the case l = 1. So we assume l > 1 below.

CONNECTIVITY OF ADDITION CAYLEY GRAPHS 9

Observe that (2) and (3) imply

l − 1 ≥ (|L| − l)(h − 1) ≥ (|L| − l)(|H| − h)(l − 1),

whence it follows from l > 1 that

(|L| − l)(|H| − h) ≤ 1.  (5)

If |H| = h, then (3) gives

l − 1 ≥ (|H| − 1)(|L| − l) ≥ (|L| − 1)(|L| − l) ≥ 2|L| − l − 2 ≥ l,

which is wrong. Therefore |H| > h. Thus we deduce from (5) and l < |L| that h = |H| − 1 and l = |L| − 1, whence (3) gives |H| = |L|. Consequently, (1) yields (S_{0} + H) \ S_{0} = (S + H) \ S, and similarly (S_{0} + L) \ S_{0} = (S + L) \ S, which (as above) proves (4) and shows that S \ S_{0} is a union of (H + L)-cosets. Furthermore, S +H misses exactly one H-coset in s_{0} +H +L, and S +L misses exactly one L-coset in s_{0} + H + L. Let g ∈ s_{0} + H + L be the common element of these two cosets, so that S_{0} + H = (s_{0} + H + L) \ (g + H) and S_{0} + L = (s_{0} + H + L) \ (g + L). Then

S_{0} ⊆ (s_{0} + H + L) \ (g + (H ∪ L)) = (g + H + L) \ (g + (H ∪ L)),

and thus

|L| − 1 = |H| − 1 ≥ |(S + H) \ S| = |(S_{0} + H) \ S_{0}| = (|L| − 1)|H| − |S_{0}|,

so that

|S_{0}| ≥ (|H| − 1)(|L| − 1) = |(g + H + L) \ (g + (H ∪ L))|.

Hence, in fact S_{0} = (g + H + L) \ (g + (H ∪ L)), completing the proof. □

Lemma 3. Let G be a finite abelian group, and suppose that the proper subset S ⊂ G, the subgroups L ≤ G_{0} ≤ G, and the element g_{0} ∈ G_{0} satisfy conditions (L1)–(L4) in the definition of L_{G}^{∗}(S). Suppose, moreover, that |S + L| − |S| ≤ |L| − 1. If H is a subgroup of G with |S + H| − |S| ≤ |H| − 1 and S + H ≠ G, then H is actually a subgroup of G_{0}.

Proof. Suppose for a contradiction that H ≰ G_{0} and fix h ∈ H \G_{0}. For each g ∈ G_{0}, we have g + h ∈ G \ G_{0} ⊆ S + L, whence g ∈ S + H + L. Hence G_{0} ⊆ S + H + L, and since, on the other hand, we have G \ G_{0} ⊆ S + L ⊆ S + H + L, we conclude that

S + H + L = G.  (6)

In view of S + H ≠ G, this leads to L ≰ H, and we let I := H ∩ L. Thus I is a proper subgroup of L.

Write n := |G_{0}/L| so that G_{0} consists of n ≥ 4 cosets of L, of which n − 1 are free of elements of S. Let {g_{i}: 0 ≤ i ≤ n − 1} be a system of representatives of these n cosets.

10 DAVID GRYNKIEWICZ, VSEVOLOD F. LEV, AND ORIOL SERRA

Fix i ∈ [1, n − 1]. Since H ≰ G_{0} and g_{i} ∈ G_{0}, we have g_{i} + H ⊈ G_{0}, whence (G \ G_{0}) ∩ (g_{i} + H) ≠ ∅; as G \ G_{0} ⊆ S + L, this yields S ∩ (g_{i} + H + L) ≠ ∅. On the other hand, from g_{i} + L ⊆ G_{0} \ (g_{0} + L) it follows that (S + L) ∩ (g_{i} + L) = ∅. Therefore,

0 < |(S + I) ∩ (g_{i} + H + L)| < |H + L|; i ∈ [1, n − 1].  (7)

In view of (6) and the hypotheses S + H ≠ G, we have S + H ≠ S + H + L and S + L ≠ S + H + L. Also, our assumptions imply

max{|S + H| − |H|, |S + L| − |L|} < |S| ≤ |S + I|,

and since both the left and right hand side are divisible by |I|, we actually have

max{|S + H| − |H|, |S + L| − |L|} ≤ |S + I| − |I|.

Thus we can apply Lemma 2. Choose g ∈ G such that (S + I) \ (g + H + L) is a union of (H + L)-cosets. Then it follows from (7) that

g_{i} + H + L = g + H + L; i ∈ [1, n − 1],  (8)

and consequently G_{0} \ (g_{0} + L) ⊆ g + H + L. Hence n ≥ 4 implies G_{0} ≤ H + L and g ∈ H + L. Thus, since S ∩ (g_{0} + L) is not contained in a coset of a proper subgroup of L, and in particular in a coset of I, we conclude that

|(S + I) ∩ (g + H + L)| = |(S + I) ∩ (g_{0} + L)| ≥ 2|I|.

This shows that Lemma 2 (i) fails. On the other hand, (8) gives g_{i} + L ⊆ g + H + L, and hence g + H + L contains at least n − 1 ≥ 3 cosets of L, all free of elements of S + I. Thus Lemma 2 (ii) fails too, a contradiction. □

4. Proofs of Theorems 2 and 3

Our starting point is the observation that if S is a subset of the finite abelian group G such that Cay_{G}^{+}(S) is not complete, then

κ(Cay_{G}^{+}(S)) = min{|(S − A) \ A|: ∅ ≠ A ⊆ G, (S − A) ∪ A ≠ G}.

For the following proposition, the reader may need to recall the notion of a fragment, introduced in Section 2 after the statement of Theorem 1.

Proposition 1. Let S be a subset of the finite abelian group G, and suppose that κ(Cay_{G}^{+}(S)) < |S|. If A is a fragment of Cay_{G}^{+}(S), then, writing H := π(S − A), we

CONNECTIVITY OF ADDITION CAYLEY GRAPHS 11

have

A ⊆ S − A,  (9)
A + H = A,  (10)
κ(Cay_{G}^{+}(S)) = |S + H| − |H|,  (11)

and

κ(Cay_{G/H}^{+} φ_{H}(S)) = |φ_{H}(S)| − 1.  (12)

Proof. Fix a ∈ A. Since a has |S| neighbors, all lying in S−A, and since |(S−A)\A| = κ(Cay_{G}^{+}(S)) < |S| by the assumptions, it follows that a has a neighbor in A; in other words, there is a′ ∈ A with a + a′ ∈ S. Consequently, a ∈ S − A, and (9) follows.

By (9) we have

(S − (A + H)) ∪ (A + H) = S − A + H = S − A ≠ G,

and obviously,

|(S − (A + H)) \ (A + H)| = |(S − A) \ (A + H)| ≤ |(S − A) \ A|.

Since A is a fragment, we conclude that in fact |(S − A) \ (A + H)| = |(S − A) \ A| holds, which gives (10).

By (9) and the assumptions, we have

|S − A| = |(S − A) \ A| + |A| = κ(Cay_{G}^{+}(S)) + |A| ≤ |S| + |A| − 1.

Hence it follows from Theorem A and (10) that

|S − A| = |S + H| + |A + H| − |H| = |S + H| + |A| − |H|.  (13)

Thus

κ(Cay_{G}^{+}(S)) = |(S − A) \ A| = |S − A| − |A| = |S + H| − |H|,

yielding (11).

Finally, we establish (12). The neighborhood of φ_{H}(A) in the graph Cay_{G/H}^{+}(φ_{H}(S)) is φ_{H}(S) − φ_{H}(A) = φ_{H}(S − A), and it follows in view of (9) that

φ_{H}(S − A) ∪ φ_{H}(A) = φ_{H}(S − A) ≠ G/H.

Consequently, the set φ_{H}(S − A) \ φ_{H}(A) is a vertex cut in Cay_{G/H}^{+}(φ_{H}(S)), whence using (9), (10), and (13) we obtain

κ(Cay_{G/H}^{+}(φ_{H}(S))) ≤ |φ_{H}(S − A) \ φ_{H}(A)| = |φ_{H}(S − A)| − |φ_{H}(A)| = (|S − A| − |A|)/|H| = |S + H|/|H| − 1 = |φ_{H}(S)| − 1.

To prove the inverse estimate, notice that the graph Cay_{G/H}^{+}(φ_{H}(S)) is not complete (we saw above that it has vertex cuts) and choose A′ ⊆ G such that φ_{H}(A′) is a

12 DAVID GRYNKIEWICZ, VSEVOLOD F. LEV, AND ORIOL SERRA

fragment of this graph. Replacing A′ with A′ + H, we can assume without loss of generality that A′ + H = A′. Since

φ_{H}((S − A′) ∪ A′) = (φ_{H}(S) − φ_{H}(A′)) ∪ φ_{H}(A′) ≠ G/H,

we have (S − A′) ∪ A′ ≠ G. Hence in view of (11) it follows that

κ(Cay_{G/H}^{+}(φ_{H}(S))) = |(φ_{H}(S) − φ_{H}(A′)) \ φ_{H}(A′)|
= |φ_{H}(S − A′) \ φ_{H}(A′)|
= |(S − A′) \ A′|/|H|
≥ |κ(Cay_{G}^{+}(S))|/|H|
= |φ_{H}(S)| − 1,

as desired. □

For a subset S of a finite abelian group G, write

λ_{G}^{∗}(S) := min{|S + L| − |L|: L ∈ L_{G}^{∗}(S)}.

Clearly, we have λ_{G}^{∗}(S) ≥ λ_{G}(S).

Lemma 4. Let S be a proper subset of the finite abelian group G. If g ∈ G, then H_{G}(S − 2g) = H_{G}(S), L_{G}^{∗}(S − 2g) = L_{G}^{∗}(S), and Cay_{G}^{+}(S − 2g) is isomorphic to Cay_{G}^{+}(S); consequently,

η_{G}(S − 2g) = η_{G}(S), λ_{G}^{∗}(S − 2g) = λ_{G}^{∗}(S),

and

κ(Cay_{G}^{+}(S − 2g)) = κ(Cay_{G}^{+}(S)).

Proof. The isomorphism between Cay_{G}^{+}(S − 2g) and Cay_{G}^{+}(S) is established by mapping every group element x to x − g, and the equality H_{G}(S − 2g) = H_{G}(S) is immediate from the observation that S + 2 ∗ G − 2g = S + 2 ∗ G. To show that L_{G}^{∗}(S − 2g) = L_{G}^{∗}(S), suppose that L ∈ L_{G}^{∗}(S) and let G_{0} ≤ G (lying above L) and g_{0} ∈ G_{0} be as in (L1)–(L4). By (L2) we have 2g ∈ G_{0}. Consequently, (G \ G_{0}) − 2g = G \ G_{0}, and hence it follows from (L4) that

S − 2g + L = (G \ G_{0}) ∪ (g_{0} − 2g + L).

Furthermore, since φ_{L}(g_{0}) is a generator of the cyclic 2-group G_{0}/L, so is φ_{L}(g_{0} − 2g); that is, ⟨g_{0} − 2g⟩ + L = G_{0}. This shows that L ∈ L_{G}^{∗}(S − 2g), and hence L_{G}^{∗}(S) ⊆ L_{G}^{∗}(S − 2g). By symmetry, we also have L_{G}^{∗}(S − 2g) ⊆ L_{G}^{∗}(S), implying the assertion. □

CONNECTIVITY OF ADDITION CAYLEY GRAPHS 13

We now pass to our last lemma, which will take us most of the way towards the proof of Theorem 2; the reader may compare the statement of this lemma with that of Theorem 1.

Lemma 5. If S is a proper subset of the finite abelian group G, then

κ(Cay_{G}^{+}(S)) = min{η_{G}(S), λ_{G}^{∗}(S), |S|}.  (14)

Proof. Since each of η_{G}(S), λ_{G}^{∗}(S), and |S| is an upper bound for κ(Cay_{G}^{+}(S)), it suffices to show that κ(Cay_{G}^{+}(S)) is greater than or equal to one of these quantities. Thus we can assume that κ(Cay_{G}^{+}(S)) ≤ |S|−1 ≤ |G|−2. Hence S ≠ ∅ and Cay_{G}^{+}(S) is not complete.

It is not difficult to see that the assertion holds true if |G| ≤ 2; we leave verification to the reader. The case |S| = 1 is also easy to establish as follows. Suppose that |G| > 2 and S = {s}, where s is an element of G. If ⟨s⟩ ≠ G, then ⟨s⟩ ∈ H_{G}(S) and |S + ⟨s⟩| − |⟨s⟩| = 0, implying κ(Cay_{G}^{+}(S)) = η_{G}(S) = 0. Next, if G is not a 2-group, then there exists an element g ∈ G which is an odd multiple of s and such that the subgroup ⟨g⟩ is proper; in this case g ∈ (S + 2 ∗ G) ∩ ⟨g⟩ showing that ⟨g⟩ ∈ H_{G}(S) and leading to κ(Cay_{G}^{+}(S)) = η_{G}(S) = 0, as above. In both cases the proof is complete, so we assume that ⟨s⟩ = G is a 2-group. Since |G| > 2, in this case we have {0} ∈ L_{G}^{∗}(S) (take G_{0} = G and g_{0} = s in (L1)–(L4)) and |S+{0}|−|{0}| = 0, whence κ(Cay_{G}^{+}(S)) = λ_{G}^{∗}(S) = 0.

Having finished with the cases |S| = 1 and |G| ≤ 2, we proceed by induction on |G|, assuming that κ(Cay_{G}^{+}(S)) ≤ |S| − 1. Choose A ⊆ G such that A is a fragment of Cay_{G}^{+}(S) and fix arbitrarily a ∈ A. In view of Lemma 4, and since the set A − a is a fragment of the graph Cay_{G}^{+}(S − 2a), by passing from S to S − 2a, and from A to A − a, we ensure that

0 ∈ A.  (15)

Also, by Proposition 1 we have A ⊆ S − A ≠ G.

If each of S and A is contained in a coset of a proper subgroup K < G, then from A ⊆ S − A and (15) it follows that in fact S and A are contained in K, whence K ∈ H_{G}(S); furthermore, |S + K| − |K| = 0, showing that κ(Cay_{G}^{+}(S)) = η_{G}(S) = 0. Accordingly, we assume for the rest of the proof that for any proper subgroup of G, at least one of the sets S and A is not contained in a coset of this subgroup.

Let H := π(S − A). We distinguish two major cases according to whether or not H is trivial.

Case 1: H is non-trivial. Applying the induction hypothesis to Cay_{G/H}^{+}(φ_{H}(S)) and using (12), we conclude that either η_{G/H}(φ_{H}(S)) = |φ_{H}(S)| − 1 or λ_{G/H}^{∗}(φ_{H}(S)) = |φ_{H}(S)| − 1, giving two subcases.

Subcase 1.1. Assume first that η_{G/H}(φ_{H}(S)) = |φ_{H}(S)| − 1, and hence that there exists a subgroup H′ ≤ G, lying above H, such that H′/H ∈ H_{G/H}(φ_{H}(S)) and

|φ_{H}(S) + H′/H| − |H′/H| = η_{G/H}(φ_{H}(S)) = |φ_{H}(S)| − 1.

The former easily implies that H′ ∈ H_{G}(S), while the latter, in conjunction with (11), implies that

|S + H′| − |H′| = |S + H| − |H| = κ(Cay_{G}^{+}(S)).

This shows that κ(Cay_{G}^{+}(S)) ≥ η_{G}(S), whence in fact κ(Cay_{G}^{+}(S)) = η_{G}(S).

Subcase 1.2. Assume now that λ_{G/H}^{∗}(φ_{H}(S)) = |φ_{H}(S)| − 1, and let L ≤ G be a subgroup, lying above H, such that L/H ∈ L_{G/H}^{∗}(φ_{H}(S)) and

|φ_{H}(S) + L/H| − |L/H| = λ_{G/H}^{∗}(φ_{H}(S)) = |φ_{H}(S)| − 1.

In view of (11) and the assumptions, the last equality yields

|S + L| − |L| = |S + H| − |H| = κ(Cay_{G}^{+}(S)) ≤ |S| − 1.  (16)

Since L/H ∈ L_{G/H}^{∗}(φ_{H}(S)), we can find a subgroup G_{0} ≤ G, lying above L, and an element g_{0} ∈ G_{0} \ L, so that G/G_{0} is an elementary abelian 2-group, G_{0}/L is a cyclic 2-group of order at least 4 generated by φ_{L}(g_{0}), and S + L = (G \ G_{0}) ∪ (g_{0} + L). Without loss of generality, we can assume that g_{0} ∈ S.

If S_{0} := S ∩ (g_{0} + L) is not contained in a coset of a proper subgroup of L, then L ∈ L_{G}^{∗}(S), and hence it follows in view of (16) that κ(Cay_{G}^{+}(S)) = λ_{G}^{∗}(S). Therefore we assume that there exists a proper subgroup R < L such that S_{0} is contained in an R-coset, and we choose R to be minimal subject to this property; thus, S_{0} = S ∩ (g_{0} + R) and ⟨(S − g_{0}) ∩ L⟩ = R.

Since S_{0} is contained in an R-coset, from (16) we obtain

|(S \ S_{0}) + L| − |S \ S_{0}| = |S + L| − |L| − |S| + |S_{0}| < |S_{0}| ≤ |R|.

Hence every R-coset in G \ G_{0} = (S \ S_{0}) + L contains at least one element of S; that is,

S + R = (G \ G_{0}) ∪ (g_{0} + R).  (17)

Consequently, using (16) once again, we obtain

|S + R| − |R| = |G \ G_{0}| = |S + L| − |L| = κ(Cay_{G}^{+}(S)).  (18)

Applying the previously completed singleton case to the set φ_{R}(S_{0}) ⊆ G_{0}/R, we get two further subcases.

CONNECTIVITY OF ADDITION CAYLEY GRAPHS 15

Subcase 1.2.1. Suppose that κ(Cay_{G_{0}/R}^{+}(φ_{R}(S_{0}))) = η_{G_{0}/R}(φ_{R}(S_{0})). Choose a subgroup R′ ≤ G_{0}, lying above R, such that R′/R ∈ H_{G_{0}/R}(φ_{R}(S_{0})). Since R ≤ R′ ≤ G_{0}, it follows in view of (17) and (18) that

|S + R′| − |R′| = |S + R| − |R| = κ(Cay_{G}^{+}(S)).

Thus, since R′ ∈ H_{G_{0}}(S_{0}) ⊆ H_{G}(S), we conclude that κ(Cay_{G}^{+}(S)) = η_{G}(S).

Subcase 1.2.2. Assume now that κ(Cay_{G_{0}/R}^{+}(φ_{R}(S_{0}))) ≠ η_{G_{0}/R}(φ_{R}(S_{0})). As |G_{0}/R| ≥ |G_{0}/L| ≥ 4, from the singleton case analysis at the beginning of the proof it follows that G_{0}/R is a cyclic 2-group generated by φ_{R}(S_{0}) = {φ_{R}(g_{0})}.

If R ∈ H_{G}(S), then it follows in view of (18) that κ(Cay_{G}^{+}(S)) = η_{G}(S); therefore, we assume that R ∉ H_{G}(S). Hence in view of S + R ⊆ S + L ≠ G we infer that 2 ∗ (G/R) ∩ φ_{R}(S) = ∅. Consequently, since (17) implies that φ_{R}(S) contains (G/R) \ (G_{0}/R) as a proper subset, we have 2 ∗ (G/R) ≨ G_{0}/R.

Applying Lemma 1, we conclude that exp(G_{0}/R) = exp(G/R). Thus (17), the remark at the beginning of the present subcase, and the above-made observation that G/G_{0} is an elementary 2-group show that R ∈ L_{G}^{∗}(S), whence (18) yields κ(Cay_{G}^{+}(S)) = λ_{G}^{∗}(S).

Case 2: H is trivial. Thus by (11) we have κ(Cay_{G}^{+}(S)) = |S| − 1, and therefore (9) gives

|S − A| − |A| = |(S − A) \ A| = κ(Cay_{G}^{+}(S)) = |S| − 1.

Applying Theorem B to the pair (S, −A), we find a subgroup F < G such that conclusions (i)–(iii) of Theorem B hold true; in particular, (φ_{F} (S), −φ_{F} (A)) is an elementary pair in G/F of one of the types (I)–(IV), and |S + F | ≤ |S| + |F | − 1. By the last inequality, we have

|S + F | − |F | ≤ |S| − 1 = κ(Cay_{G}^{+}(S)).

Hence, if F ∈ H_{G}(S), then κ(Cay_{G}^{+}(S)) = η_{G}(S); consequently, we assume that

F ∉ H_{G}(S).  (19)

Observe that if φ_{F} (S) = G/F, then F is non-zero, whence by Theorem B (iii) we have |φ_{F} (A)| = 1. Thus, if (φ_{F} (S), −φ_{F} (A)) is not of type (I), then

S + F ≠ G.  (20)

We proceed by cases corresponding to the type of the pair (φ_{F} (S), −φ_{F} (A)).

16 DAVID GRYNKIEWICZ, VSEVOLOD F. LEV, AND ORIOL SERRA

Subcase 2.1. Suppose that (φ_{F} (S), −φ_{F} (A)) is of type (IV). In this case, we have μ(φ_{F} (S), −φ_{F} (A)) ≥ 2, whence it follows by Theorem B (iii) that F is trivial. Hence (S, −A) is an elementary pair of type (IV). Thus, since S and A are not both contained in a coset of the same proper subgroup, it follows that A = g+(G\S) for some g ∈ G, implying −g ∉ S − A. Therefore (9) yields −g ∉ g + (G \ S) and thus −2g ∈ S; consequently, {0} = F ∈ H_{G}(S), contradicting (19).

Subcase 2.2. Suppose that (φ_{F} (S), −φ_{F} (A)) is of type (III), but not of type (I). Then, since S and A are not both contained in a coset of the same proper subgroup and since S − A ≠ G, it follows that F is non-zero, that

φ_{F} (S) = φ_{F} (g_{1}) + (H_{1} ∪ {0}), −φ_{F} (A) = φ_{F} (g_{2}) − (H_{2} ∪ {0})

for some g_{1}, g_{2} ∈ G, where H_{1} ∪ H_{2} ∪ {0} is a partition of G/F, and that g_{1} + g_{2} + F has a non-empty intersection with S − A, while every F -coset, other than g_{1} + g_{2} + F, is contained in S − A; moreover, from π(S − A) = {0} we derive that

g_{1} + g_{2} + F ⊈ S − A.  (21)

By Theorem B, all F -cosets corresponding to

(−φ_{F} (A)) \ {φ_{F} (g_{2})} = φ_{F} (g_{2}) − H_{2},

are contained in −A. Hence, if

−φ_{F} (g_{1} + g_{2}) ∈ φ_{F} (g_{2}) − H_{2},

then −g_{1} − g_{2} + F ⊆ −A, and it follows in view of (9) that g_{1} + g_{2} + F ⊆ A ⊆ S − A, contradicting (21). Therefore, assume instead that −φ_{F} (g_{1} + g_{2}) ∉ φ_{F} (g_{2}) − H_{2}, so that φ_{F} (g_{1} + 2g_{2}) ∈ H_{1} ∪ {0}. Then 2φ_{F} (g_{1} + g_{2}) ∈ φ_{F} (g_{1}) + (H_{1} ∪ {0}) = φ_{F} (S), whence by (20) we have F ∈ H_{G}(S), contradicting (19).

Subcase 2.3. Suppose that (φ_{F} (S), −φ_{F} (A)) is of type (II), but not of type (I). Letting u := |φ_{F} (S)| and v := |φ_{F} (A)|, and choosing s_{0} ∈ S, a_{0} ∈ A, and d ∈ G \ {0} appropriately, we write

φ_{F} (S) = {φ_{F} (s_{0}), φ_{F} (s_{0}) + φ_{F} (d), …, φ_{F} (s_{0}) + (u − 1)φ_{F} (d)}

and

−φ_{F} (A) = {φ_{F} (a_{0}), φ_{F} (a_{0}) + φ_{F} (d), …, φ_{F} (a_{0}) + (v − 1)φ_{F} (d)}.

Since (φ_{F} (S), −φ_{F} (A)) is not of type (I), we have u, v ≥ 2. Next, it follows from (9) that

−φ_{F} (a_{0}) = φ_{F} (s_{0}) + φ_{F} (a_{0}) + rφ_{F} (d),

CONNECTIVITY OF ADDITION CAYLEY GRAPHS 17

and therefore φ_{F} (s_{0}) = −2φ_{F} (a_{0}) − rφ_{F} (d), for some integer r. Thus either φ_{F} (s_{0}) (if r is even) or φ_{F} (s_{0}) + φ_{F} (d) (if r is odd) belongs to 2 ∗ (G/F). In either case, in view of u ≥ 2 we have φ_{F} (S) ∩ (2 ∗ (G/F)) ≠ ∅, which by (20) leads to F ∈ H_{G}(S), contradicting (19).

Subcase 2.4. Finally, suppose that (φ_{F} (S), −φ_{F} (A)) is of type (I); that is, either |φ_{F} (S)| = 1 or |φ_{F} (A)| = 1 holds.

Suppose first that |φ_{F} (S)| = 1. In this case, F is non-zero (as |S| > 1) and S + F ≠ G (as F is a proper subgroup); moreover, from (9) we obtain

φ_{F} (S) − φ_{F} (A) = φ_{F} (A).  (22)

By Theorem B, we can write A = A_{1} ∪A_{0}, where A_{1} is a union of F -cosets and A_{0} is a non-empty subset of an F -coset disjoint from A_{1}. If φ_{F} (S) − φ_{F} (A_{0}) ⊆ φ_{F} (A_{1}), then S − A_{0} + F ⊆ A_{1} + F = A_{1} ⊆ S − A, whence S − A = (S − A_{1}) ∪ (S − A_{0}) is a union of F -cosets, contradicting the assumption that S − A is aperiodic. Therefore (22) gives φ_{F} (S)−φ_{F} (A_{0}) = φ_{F} (A_{0}), which together with S +F ≠ G implies F ∈ H_{G}(S), contradicting (19). So we assume for the remainder of the proof that |φ_{F} (S)| > |φ_{F} (A)| = 1, and consequently in view of (15) that A ⊆ F.

Thus from (9) we derive that 0 ∈ φ_{F} (S), and it follows in view of (19) that S + F = G. Hence F is nontrivial, and Theorem B shows that there exists s_{0} ∈ S such that S = (G \ (s_{0} + F)) ∪ S_{0}, where S_{0} ⊂ s_{0} + F.

If there exists g ∈ G with φ_{F} (g) ≠ −φ_{F} (g) + φ_{F} (s_{0}), then it follows in view of φ_{F} (S) = G/F that φ_{F} (g) ∈ −φ_{F} (g) + φ_{F} (S \ S_{0}), whence

g ∈ −g + (S \ S_{0}) + F ⊆ −g + S;

consequently, {0} ∈ H_{G}(S) and κ(Cay_{G}^{+}(S)) = η_{G}(S). Therefore we assume that φ_{F} (g) = −φ_{F} (g) + φ_{F} (s_{0}) for all g ∈ G. Hence 2 ∗ (G/F) = {φ_{F} (s_{0})}, which implies that G/F is an elementary 2-group and that φ_{F} (s_{0}) = 0; consequently, S_{0} = S ∩ F.

From A ⊆ F and (9), it follows that A ⊆ (S −A)∩F = S_{0}−A, and since S −A ≠ G and S + F = G we have S_{0} − A ≠ F. Consequently, Theorem B (i) yields

κ(Cay_{F}^{+}(S_{0})) ≤ |(S_{0} − A) \ A| = |S_{0} − A| − |A| ≤ |S_{0}| − 1.  (23)

Since S_{0} is a proper subset of F, it follows in view of (23) that κ(Cay_{F}^{+}(S_{0})) ≤ |F |−2, whence Cay_{F}^{+}(S_{0}) is not complete. Let A′ ⊆ F be a fragment of Cay_{F}^{+}(S_{0}). By (9) and 23, we have A′ ⊆ S_{0} − A′ ≠ F, and consequently A′ ⊆ S − A′ ≠ G. Hence from (23) and S \ S_{0} = G \ F we obtain

|S| − 1 = κ(Cay_{G}^{+}(S)) ≤ |(S − A′) \ A′| ≤ |G \ F | + |(S_{0} − A′) \ A′| = |S \ S_{0}| + κ(Cay_{F}^{+}(S_{0})) ≤ |S| − 1,

18 DAVID GRYNKIEWICZ, VSEVOLOD F. LEV, AND ORIOL SERRA

implying κ(Cay_{F}^{+}(S_{0})) = |S_{0}| − 1 and

κ(Cay_{G}^{+}(S)) = |S \ S_{0}| + κ(Cay_{F}^{+}(S_{0})).

Consequently, if F′ ≤ F has the property that κ(Cay_{F}^{+}(S_{0})) = |S_{0} + F′| − |F′|, then

κ(Cay_{G}^{+}(S)) = |S + F′| − |F′|.  (24)

With (23) in mind, we apply the induction hypothesis to the graph Cay_{F}^{+}(S_{0}). If κ(Cay_{F}^{+}(S_{0})) = η_{F} (S_{0}), then by (24) any subgroup F′ ∈ H_{F} (S_{0}) ⊆ H_{G}(S) with κ(Cay_{F}^{+}(S_{0})) = |S_{0} + F′| − |F′| satisfies κ(Cay_{G}^{+}(S)) = |S + F′| − |F′|, whence κ(Cay_{G}^{+}(S)) = η_{G}(S). Therefore we assume instead that κ(Cay_{F}^{+}(S_{0})) = λ_{F}^{∗} (S_{0}).

Choose L ∈ L_{F}^{∗} (S_{0}) with λ_{F}^{∗} (S_{0}) = |S_{0} + L| − |L|, and let G_{0} and g_{0} ∈ G_{0} be as in (L1)–(L4), with F playing the role of G. Then it follows in view of (24) that

κ(Cay_{G}^{+}(S)) = |S + L| − |L|.  (25)

If φ_{L}(S) ∩ 2 ∗ (G/L) ≠ ∅, then L ∈ H_{G}(S), whence (25) yields κ(Cay_{G}^{+}(S)) = η_{G}(S). Therefore we assume that

φ_{L}(S) ∩ 2 ∗ (G/L) = ∅  (26)

and we proceed to show that L ∈ L_{G}^{∗}(S); in view of (25), this will complete the proof.

Since L ∈ L_{F}^{∗} (S_{0}), and by the choice of G_{0} and g_{0}, we see that G_{0}/L is a cyclic 2group with |G_{0}/L| ≥ 4 and ⟨g_{0}⟩+L = G_{0}; furthermore, S∩(g_{0}+L) is not contained in a proper coset of L, and S_{0} +L = (F \G_{0})∪(g_{0} +L), which in view of S = (G\F)∪S_{0} and L ≤ F yields

S + L = (G \ G_{0}) ∪ (g_{0} + L).  (27)

It remains to show that exp(G/L) = exp(G_{0}/L) and that G/G_{0} is an elementary 2group. To prove the former, we observe that (26) and (27) yield 2∗(G/L) ≨ G_{0}/L and invoke Lemma 1. To establish the latter, simply observe that G/(2 ∗ G) is in general an elementary 2-group, and that 2 ∗ (G/L) ≨ G_{0}/L implies 2 ∗ G ≤ G_{0} + L = G_{0}. □

We can now prove Theorem 2.

Proof of Theorem 2. We first show that there is at most one subgroup L ∈ L_{G}^{∗}(S) with

|S + L| − |L| ≤ |S| − 1.  (28)

For a contradiction, assume that L, L′ ∈ L_{G}^{∗}(S) are distinct, L satisfies (28), and |S + L′| − |L′| ≤ |S| − 1. Find G_{0} ≤ G and g_{0} ∈ G_{0} such that (L1)–(L4) hold, and let S_{0} = S ∩ (g_{0} + L). It follows from Lemma 3 that L′ ≤ G_{0}, whence

|L′| − 1 ≥ |S + L′| − |S| ≥ |S_{0} + L′| − |S_{0}|.  (29)

CONNECTIVITY OF ADDITION CAYLEY GRAPHS 19

Suppose that L ≰ L′ and L′ ≰ L, and write t = φ_{L′}(S_{0}); that is, t is the number of L′-cosets that intersect S_{0}. Since S_{0} is not contained in a proper coset of L, and since L ≰ L′, we have t ≥ 2. Consequently, from L′ ≰ L it follows that

|S_{0} + L′| − |S_{0}| ≥ t(|L′| − |L ∩ L′|) ≥ t|L′|/2 ≥ |L′|,

contradicting (29). So we may assume either L ≤ L′ or L′ ≤ L; switching the notation, if necessary, and recalling that L′ ≠ L, we assume that L < L′.

Since L′ ∈ L_{G}^{∗}(S), there exists a subgroup G′_{0} ≤ G, lying above L′, and an element g′_{0} ∈ G′_{0} such that |G′_{0}| ≥ 4|L′|, (S + L′) \ (g′_{0} + L′) = G \ G′_{0}, and (g′_{0} + L′) ∩ S is not contained in a proper coset of L′. If φ_{L′}(g′_{0}) = φ_{L′}(g_{0}), then (g′_{0} + L′) ∩ S = (g_{0} + L′) ∩ S, while, in view of L′ ≤ G_{0}, the right-hand side is contained in an Lcoset, which, in view of L < L′, contradicts that (g′_{0} + L′) ∩ S is not contained in a proper coset of L′. Therefore, we conclude instead that φ_{L′}(g_{0}) ≠ φ_{L′}(g′_{0}). Thus, since |π(φ_{L′}(S) \ {φ_{L′}(g′_{0})})| = |π(G′_{0}/L′)| ≥ 4, it follows from Proposition A that |π(φ_{L′}(S) \ {φ_{L′}(g_{0})})| = 1, which is equivalent to

π((S + L′) \ (g_{0} + L′)) = L′.

Hence, since L < L′ ≤ G_{0}, so that (S + L′) \ (g_{0} + L′) = G \ G_{0}, it follows that L′ = G_{0}, whence S + L′ = S + G_{0} = G, contradicting the assumption L′ ∈ L_{G}^{∗}(S). This establishes uniqueness of L ∈ L_{G}^{∗}(S) satisfying (28).

Clearly, Lemma 5 implies assertion (ii) of Theorem 2, and therefore it remains to establish assertion (i). To this end, suppose that L ∈ L_{G}^{∗}(S) satisfies (28), and that G_{0} and g_{0} are as in (L1)–(L4). We will show that η_{G}(S) ≥ |S| and κ(Cay_{G}^{+}(S)) = λ_{G}(S) = λ_{G}^{∗}(S) = |S + L| − |L|.

Suppose that there exists H ∈ H_{G}(S) with

|S + H| − |H| ≤ |S| − 1.  (30)

Then H ≤ G_{0} by Lemma 3. If H ≤ L, then from (S + 2 ∗ G) ∩ H ≠ ∅ we obtain (S + 2 ∗ G) ∩ L ≠ ∅, contradicting (L1)–(L4). Therefore H ≰ L.

Let S_{0} = (g_{0} + L) ∩ S, and denote by t the number of H-cosets intersecting S_{0}. In view of (30), and taking into account H ≤ G_{0} and H ≰ L, we obtain

|H| − 1 ≥ |S + H| − |S| ≥ |S_{0} + H| − |S_{0}| ≥ t(|H| − |H ∩ L|) ≥ t|H|/2.

Hence t = 1. Thus, since S_{0} is not contained in a coset of a proper subgroup of L, we conclude that L ≤ H. Consequently, from (L1)–(L3) we get 2 ∗ (G/H) = 2 ∗ (G_{0}/H), and thus, in view of (S + 2 ∗ G) ∩ H ≠ ∅ and taking into account (L4), we have

∅ ≠ φ_{H}(S) ∩ 2 ∗ (G/H) = φ_{H}(S) ∩ 2 ∗ (G_{0}/H) = {φ_{H}(g_{0})} ∩ 2 ∗ (G_{0}/H). (31)

20 DAVID GRYNKIEWICZ, VSEVOLOD F. LEV, AND ORIOL SERRA

Since φ_{L}(g_{0}) generates G_{0}/L, it follows from H ≥ L that φ_{H}(g_{0}) generates the cyclic 2-group G_{0}/H. Thus (31) implies that H = G_{0}, whence S + H = S + G_{0} = G, a contradiction. So we conclude that there are no subgroups H ∈ H_{G}(S) satisfying (30); that is, η_{G}(S) ≥ |S|. Thus it follows by Lemma 5 that

κ(Cay_{G}^{+}(S)) = min{λ_{G}^{∗}(S), |S|}.  (32)

The uniqueness of L, established above, implies that λ_{G}^{∗}(S) = |S + L| − |L|, and now (28) shows that

κ(Cay_{G}^{+}(S)) ≤ λ_{G}(S) ≤ λ_{G}^{∗}(S) = |S + L| − |L| ≤ |S| − 1.

Comparing this with (32), we see that, indeed, the first two inequalities are actually equalities. □

Finally, we prove Theorem 3.

Proof of Theorem 3. By Theorem 2, we have κ(Cay_{G}^{+}(S)) = |S + L| − |L| with a subgroup L ≤ G, belonging to either H_{G}(S) or L_{G}^{∗}(S). Let F ≤ G be a subgroup that minimizes |S + F | − |F | over all subgroups with S + F ≠ G. Assuming that

|S + F | − |F | < |S + L| − |L| ≤ |S| − 1,  (33)

we will obtain a contradiction; evidently, this will prove the assertion.

¿From Lemma 2 and (33), it follows that either S + F + L = S + L or S + F + L = S + F; in either case,

S + F + L ≠ G.  (34)

Suppose first that |L| ≤ |F |. Then Lemma 2 yields S + F + L = S + F, and thus

|S + F + L| − |F + L| = |S + F | − |F + L|.

The minimality of F now implies that |F + L| = |F |, whence L ≤ F. If L ∈ H_{G}(S), then it follows in view of L ≤ F and S + F ≠ G that F ∈ H_{G}(S), implying κ(Cay_{G}^{+}(S)) ≤ |S + F | − |F |. However, since κ(Cay_{G}^{+}(S)) = |S + L| − |L|, this contradicts (33). Therefore we may assume L ∈ L_{G}^{∗}(S). Let G_{0} be the subgroup from the definition of L_{G}^{∗}(S). By Lemma 3 we then have L ≤ F ≤ G_{0}, whence

|S + F | = |G \ G_{0}| + |F | = (|S + L| − |L|) + |F |,

which contradicts (33) once more.

Next, suppose that |F | ≤ |L|. Thus it follows by Lemma 2 that S +L = S +F +L. Hence

|S + F + L| − |F + L| = |S + L| − |F + L|.  (35)

If L ∈ H_{G}(S), then it follows in view of L ≤ F + L and (34) that F + L ∈ H_{G}(S); now (35) and the minimality of L give |F + L| = |L|, leading to F ≤ L. We proceed to show that this holds in the case L ∈ L_{G}^{∗}(S) as well. In this case, in view of (35) and (33), Lemma 3 gives F + L ≤ G_{0}, where G_{0} is the subgroup from the definition of L_{G}^{∗}(S). Thus (as in the previous paragraph)

|S + F + L| = |G \ G_{0}| + |F + L| = (|S + L| − |L|) + |F + L|.

Hence, since |S + F + L| = |S + L|, we obtain |F + L| = |L|, and therefore F ≤ L, as desired.

We have just shown that F ≤ L holds true in either case. Consequently, from |S + L| − |L| < |S| ≤ |S + F | and divisibility considerations, it follows that indeed |S + L| − |L| ≤ |S + F | − |F |, contradicting (33) and completing the proof. □

References

[A] N. Alon, Large sets in finite fields are sumsets, J. Number Theory, to appear.

[CGW03] B. Cheyne, V. Gupta, and C. Wheeler, Hamilton Cycles in Addition Graphs, Rose-Hulman Undergraduate Math. Journal 1 (4) (2003) (electronic).

[C92] F.R.K. Chung, Diameters and eigenvalues, J. Amer. Math. Soc. 2 (2) (1989), 187–196.

[Gr05] B.J. Green, Counting sets with small sumset, and the clique number of random Cayley graphs, Combinatorica 25 (2005), 307–326.

[Gk01] D.J. Grynkiewicz, Quasi-periodic decompositions and the Kemperman structure theorem, European Journal of Combinatorics 26 (5) (2005), 559–575.

[Gk02] , Sumsets, Zero-Sums and Extremal Combinatorics, Ph.D. Dissertation, Caltech (2005).

[Km60] J.H.B. Kemperman, On small subsets in an abelian group, Acta Mathematica 103 (1960), 63–88.

[Kn53] M. Kneser, Abschätzung der asymptotischen Dichte von Summenmengen, Math. Z. 58 (1953), 459–484.

[Kn55] , Ein Satz über abelsche Gruppen mit Anwendungen auf die Geometrie der Zahlen, Math. Z. 61 (1955), 429–434.

[L05] V.F. Lev, Critical pairs in abelian groups and Kemperman’s structure theorem, Internation Journal of Number Theory 2 (3) (2006), 379–396.

[L] , Sums and differences along Hamiltonian cycles, Submitted.

[Mn76] H.B. Mann, Addition theorems: the addition theorems of group theory and number theory. Reprint, with corrections, of the 1965 original. Robert E. Krieger Publishing Co., Huntington, N.Y., 1976.

[Mr83] D. Marušič, Hamiltonian circuits in Cayley graphs, Discrete Math. 46 (1) (1983), 49–54.

Departament de Matemàtica Aplicada IV, Universitat Politècnica de Catalunya, Campus Nord Edifici C3, Jordi Girona Salgado 1-3, Barcelona, Catalonia E-08034, Spain.

E-mail address: diambri@hotmail.com

Department of Mathematics, University of Haifa at Oranim, Tivon 36006, Israel

E-mail address: seva@math.haifa.ac.il

Departament de Matemàtica Aplicada IV, Universitat Politècnica de Catalunya, Campus Nord Edifici C3, Jordi Girona Salgado 1-3, Barcelona, Catalonia E-08034, Spain

E-mail address: oserra@ma4.upc.edu