The Number of <Emphasis Type="Italic">k</Emphasis>-Sumsets in an Abelian Group

Let G be an abelian group of order n. The sum of subsets A₁,...,A_k of G is defined as the collection of all sums of k elements from A₁,...,A_k; i.e., A₁ + A₂ + · · · + A_k = {a₁ + · · · + a_k | a₁ ∈ A₁,..., a_k ∈ A_k}. A subset representable as the sum of k subsets of G is a k-sumset. We consider the problem of the number of k-sumsets in an abelian group G. It is obvious that each subset A in G is a k-sumset since A is representable as A = A₁ + · · · + A_k, where A₁ = A and A₂ = · · · = A_k = {0}. Thus, the number of k-sumsets is equal to the number of all subsets of G. But, if we introduce a constraint on the size of the summands A₁,...,A_k then the number of k-sumsets becomes substantially smaller. A lower and upper asymptotic bounds of the number of k-sumsets in abelian groups are obtained provided that there exists a summand A_i such that |A_i| = n log^qn and |A₁ +· · ·+ A_i-1 + A_i+1 + · · ·+A_k| = n log^qn, where q = -1/8 and i ∈ {1,..., k}.     

Torsion units in integral group rings of some metabelian groups,II

We prove that any torsion unit of the integral group ring ZG is rationally conjugate to a trivial unit if G = A ⋊ X with both A and X abelian, |Xz.sfnc; < p for every prime p dividing |A| provided either |X| is prime or A ic cyclic.     

Torsion units in integral group rings of metacyclic groups

It is proved that if G is a split extension of a cyclic p-group by a cyclic p′-group with faithful action then any torsion unit of augmentation one of $\text{Z}$G is rationally conjugate to a group element. It is also proved that if G is a split extension of an abelian group A by an abelian group X with (|A|, |X|) = 1 then any torsion unit of $\text{Z}$G of augmentation one and order relatively prime to |A| is rationally conjugate to an element of X.     

On sum sets of sidon sets,II

LetG be a finite abelian group,G?{Z _n, Z₂?Z_2n}. Then every sequenceA={g ₁,...,g_t} of $t = \frac{{4\left| G \right|}}{3} + 1$ elements fromG contains a subsequenceB?A, |G|=|G| such that $\sum\nolimits_{g_i \in B^{g_i } } { = 0 (in G)} $ . This bound, which is best possible, extends recent results of [1] and [22] concerning the celebrated theorem of Erdös-Ginzburg-Ziv [21].     

On integral Cayley sum graphs

Let S be a subset of a finite abelian group G. The Cayley sum graph Cay⁺(G, S) of G with respect to S is a graph whose vertex set is G and two vertices g and h are joined by an edge if and only if g + h ∈ S. We call a finite abelian group G a Cayley sum integral group if for every subset S of G, Cay⁺(G, S) is integral i.e., all eigenvalues of its adjacency matrix are integers. In this paper, we prove that all Cayley sum integral groups are represented by Z₃ and Zn₂ ⁿ, n ≥ 1, where Z_k is the group of integers modulo k. Also, we classify simple connected cubic integral Cayley sum graphs.     

Degree conditions for group connectivity

Let G be a 2-edge-connected simple graph on n≥13 vertices and A an (additive) abelian group with |A|≥4. In this paper, we prove that if for every uv∉E(G), max{d(u),d(v)}≥n/4, then either G is A-connected or G can be reduced to one of K_2,3,C₄ and C₅ by repeatedly contracting proper A-connected subgraphs, where C_k is a cycle of length k. We also show that the bound n≥13 is the best possible.     

Davenport constant with weights and some related questions, II

Let G be a finite abelian group of order n and let A⊆Z be non-empty. Generalizing a well-known constant, we define the Davenport constant of G with weight A, denoted by DA(G), to be the least natural number k such that for any sequence (x₁,…,xk) with xi∈G, there exists a non-empty subsequence (xj₁,…,xjl) and a₁,…,al∈A such that . Similarly, for any such set A, EA(G) is defined to be the least t∈N such that for all sequences (x₁,…,xt) with xi∈G, there exist indices j₁,…,jn∈N,1?j₁<?<jn?t, and ?₁,…,?n∈A with . In the present paper, we establish a relation between the constants DA(G) and EA(G) under certain conditions. Our definitions are compatible with the previous generalizations for the particular group G=Z/nZ and the relation we establish had been conjectured in that particular case.     

Arithmetic-progression-weighted subsequence sums

Let G be an abelian group, let s be a sequence of terms s ₁, s ₂, …, s _n ∈ G not all contained in a coset of a proper subgroup of G, and let W be a sequence of n consecutive integers. Let $$W \odot S = \left\{ {w_1 s_1 + \cdots + w_n s_n :w_i a term of W,w_i \ne w_j for i \ne j} \right\},$$ which is a particular kind of weighted restricted sumset. We show that |W ⊙ S| ≥ min{|G| ? 1, n}, that W ⊙ S = G if n ≥ |G| + 1, and also characterize all sequences S of length |G| with W ⊙ S ≠ G. This result then allows us to characterize when a linear equation $$a_1 x_1 + \cdots + a_r x_r \equiv \alpha mod n,$$ where α, a ₁, …, a _r ∈ ? are given, has a solution (x ₁, …, x _r ) ∈ ? ^r modulo n with all x _i distinct modulo n. As a second simple corollary, we also show that there are maximal length minimal zero-sum sequences over a rank 2 finite abelian group $G \cong C_{n_1 } \oplus C_{n_2 }$ (where n ₁ |n ₂ and n ₂ ≥ 3) having k distinct terms, for any k ε [3, min{n ₁ + 1, exp(G)}]. Indeed, apart from a few simple restrictions, any pattern of multiplicities is realizable for such a maximal length minimal zero-sum sequence.     

Group Connectivity of Bridged Graphs

Let G be a 2-edge-connected simple graph, and let A denote an abelian group with the identity element 0. If a graph G ^* is obtained by repeatedly contracting nontrivial A-connected subgraphs of G until no such a subgraph left, we say G can be A-reduced to G*. A graph G is bridged if every cycle of length at least 4 has two vertices x, y such that d _G (x, y) < d _C (x, y). In this paper, we investigate the group connectivity number Λ _g (G) = min{n: G is A-connected for every abelian group with |A| ≥ n} for bridged graphs. Our results extend the early theorems for chordal graphs by Lai (Graphs Comb 16:165–176, 2000) and Chen et al. (Ars Comb 88:217–227, 2008).     

Additive Latin transversals and group rings

LetA={a ₁, …,a _k} and {b ₁, …,b _k} be two subsets of an abelian groupG, k≤|G|. Snevily conjectured that, when |G| is odd, there is a numbering of the elements ofB such thata _i+b _i,1≤i≤k are pairwise distinct. By using a polynomial method, Alon affirmed this conjecture for |G| prime, even whenA is a sequence ofk<|G| elements. With a new application of the polynomial method, Dasgupta, Károlyi, Serra and Szegedy extended Alon’s result to the groupsZ _p ^r andZ _p ^rin the casek<p and verified Snevily’s conjecture for every cyclic group. In this paper, by employing group rings as a tool, we prove that Alon’s result is true for any finite abelianp-group withk<√2p, and verify Snevily’s conjecture for every abelian group of odd order in the casek<√p, wherep is the smallest prime divisor of |G|. This work has been supported partly by NSFC grant number 19971058 and 10271080.     

Complexity of representation of graphs by set systems

Let $\text{F}$ be a family of subsets of S and let G be a graph with vertex set $\text{V={x}{}_{\mathrm{A}}\text{|A ∈}\text{F}\text{}}$ such that: (x_A, x_B) is an edge iff $\text{A?B≠}\text{0}\text{/}$. The family $\text{F}$ is called a set representation of the graph G.It is proved that the problem of finding minimum k such that G can be represented by a family of sets of cardinality at most k is NP-complete. Moreover, it is NP-complete to decide whether a graph can be represented by a family of distinct 3-element sets.The set representations of random graphs are also considered.     

Note on group distance magic complete bipartite graphs

A Γ-distance magic labeling of a graph G = (V, E) with |V| = n is a bijection ? from V to an Abelian group Γ of order n such that the weight $w(x) = \sum\nolimits_{y \in N_G (x)} {\ell (y)}$ of every vertex x ∈ V is equal to the same element µ ∈ Γ, called the magic constant. A graph G is called a group distance magic graph if there exists a Γ-distance magic labeling for every Abelian group Γ of order |V(G)|. In this paper we give necessary and sufficient conditions for complete k-partite graphs of odd order p to be ? _p -distance magic. Moreover we show that if p ≡ 2 (mod 4) and k is even, then there does not exist a group Γ of order p such that there exists a Γ-distance labeling for a k-partite complete graph of order p. We also prove that K _m,n is a group distance magic graph if and only if n + m ? 2 (mod 4).     

Progression-free sets in finite abelian groups

Let G be a finite abelian group. Write and denote by rk(2G) the rank of the group 2G.Extending a result of Meshulam, we prove the following. Suppose that A⊆G is free of “true” arithmetic progressions; that is, a₁+a₃=2a₂ with a₁,a₂,a₃∈A implies that a₁=a₃. Then |A|<2|G|/rk(2G). When G is of odd order this reduces to the original result of Meshulam.As a corollary, we generalize a result of Alon and show that if an integer k?2 and a real ε>0 are fixed, |2G| is large enough, and a subset A⊆G satisfies |A|?(1/k+ε)|G|, then there exists A₀⊆A such that 1?|A₀|?k and the elements of A₀ add up to zero. When G is of odd order or cyclic this reduces to the original result of Alon.     

Minimal sumsets in finite solvable groups

Given a group G and positive integers r,s≤|G|, we denote by μ_G(r,s) the least possible size of a product set AB={ab∣a∈A,b∈B}, where A,B run over all subsets of G of size r,s, respectively. While the function μ_G is completely known when G is abelian [S. Eliahou, M. Kervaire, Minimal sumsets in infinite abelian groups, Journal of Algebra 287 (2005) 449-457], it is largely unknown for G non-abelian, in part because efficient tools for proving lower bounds on μ_G are still lacking in that case. Our main result here is a lower bound on μ_G for finite solvable groups, obtained by building it up from the abelian case with suitable combinatorial arguments. The result may be summarized as follows: if G is finite solvable of order m, then μ_G(r,s)≥μ_G^′(r,s), where G^′ is any abelian group of the same order m. Equivalently, with our knowledge of μ_G^′, our formula reads .One nice application is the full determination of the function μ_G for the dihedral group G=D_n and all n≥1. Up to now, only the case where n is a prime power was known. We prove that, for all n≥1, the group D_n has the same μ-function as an abelian group of order |D_n|=2n.     

Degree conditions and degree bounded trees

We give sufficient conditions for a graph to have degree bounded trees. Let G be a connected graph and A a vertex subset of G. We denote by σ_k(A) the minimum value of the degree sum in G of any k independent vertices in A and by w(G−A) the number of components in the induced subgraph G−A. Our main results are the following: (i) If σ_k(A)≥|V(G)|−1, then G contains a tree T with maximum degree at most k and A⊆V(T). (ii) If σ_k−w(G−A)(A)≥|A|−1, then G contains a spanning tree T such that d_T(x)≤k for every x∈A. These are generalizations of the result by Win [S. Win, Existenz von Gerüsten mit Vorgeschriebenem Maximalgrad in Graphen, Abh. Math. Sem. Univ. Hamburg 43 (1975) 263-267] and the degree conditions are sharp.     

A subgroup involvement of the Fibonacci length

For a non-Abelian 2-generated finite group G=〈a,b〉, the Fibonacci length of G with respect to A={a,b}, denoted by LEN _A (G), is defined to be the period of the sequence x ₁=a,x ₂=b,x ₃=x ₁ x ₂,…,x _n+1=x _n?1 x _n ,… of the elements of G. For a finite cyclic group C _n =〈a〉, LEN _A (C _n ) is defined in a similar way where A={1,a} and it is known that LEN _A (C _n )=k(n), the well-known Wall number of n. Over all of the interesting numerical results on the Fibonacci length of finite groups which have been obtained by many authors since 1990, an intrinsic property has been studied in this paper. Indeed, by studying the family of minimal non-Abelian p-groups it will be shown that for every group G of this family, there exists a suitable generating set A′ for the derived subgroup G′ such that LEN _A′(G′)|LEN _A (G) where, A is the original generating set of G.     

On the extendability of Bi-Cayley graphs of finite abelian groups

Let G be a finite group and A a nonempty subset (possibly containing the identity element) of G. The Bi-Cayley graph X=BC(G,A) of G with respect to A is defined as the bipartite graph with vertex set G×{0,1} and edge set {{(g,0),(sg,1)}∣g∈G,s∈A}. A graph Γ admitting a perfect matching is called n-extendable if ∣V(Γ)∣≥2n+2 and every matching of size n in Γ can be extended to a perfect matching of Γ. In this paper, the extendability of Bi-Cayley graphs of finite abelian groups is explored. In particular, 2-extendable and 3-extendable Bi-Cayley graphs of finite abelian groups are characterized.     

Arbitrary torsion classes and almost free abelian groups

Using the set theoretical principle ? for arbitrary large cardinals κ, arbitrary large strongly κ-free abelian groupsA are constructed such that Hom(A, G)={0} for all cotorsion-free groupsG with |G|<κ. This result will be applied to the theory of arbitrary torsion classes for Mod-Z. It allows one, in particular, to prove that the classF of cotorsion-free abelian groups is not cogenerated by aset of abelian groups. This answers a conjecture of Göbel and Wald positively. Furthermore, arbitrary many torsion classes for Mod-Z can be constructed which are not generated or not cogenerated by single abelian groups.     

Abelian 2-class field towers over the cyclotomic {\mathbb {Z}_2}-extensions of imaginary quadratic fields

For the cyclotomic \mathbb Z₂{\mathbb Z_2}-extension k _∞ of an imaginary quadratic field k, we consider whether the Galois group G(k _∞) of the maximal unramified pro-2-extension over k _∞ is abelian or not. The group G(k _∞) is abelian if and only if the nth layer of the \mathbb Z₂{\mathbb {Z}_2}-extension has abelian 2-class field tower for all n ≥ 1. The purpose of this paper is to classify all such imaginary quadratic fields k in part by using Iwasawa polynomials.     

Achievement and avoidance games for generating abelian groups

For any finite groupG, the DO GENERATE game is played by two players Alpha and Beta as follows. Alpha moves first and choosesx ₁ ∈G. Thek-th play consists of a choice ofx _k ∈G ?S _k ?1 whereS _n ={itx ₁,...,x _n }. LetG _n = 〈S _n 〉. The game ends whenG _n =G. The player who movesx _n wins. In the corresponding avoidance game, DON'T GENERATE, the last player to move loses. Of course neither game can end in a draw. For an arbitrary group, it is an unsolved problem to determine whether Alpha or Beta wins either game. However these two questions are answered here for abelian groups.