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.     

Additive latin transversals

We prove that for every odd primep, everyk≤p and every two subsets A={a ₁, …,a _k } andB={b ₁, …,b _k } of cardinalityk each ofZ _p , there is a permutationπ ∈S _k such that the sumsa _i +b _π(i) (inZ _p ) are pairwise distinct. This partially settles a question of Snevily. The proof is algebraic, and implies several related results as well. Research supported in part by a State of New Jersey grant and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University.     

Exterior algebras and two conjectures on finite abelian groups

Let G be a finite abelian group with |G| > 1. Let a ₁, …, a _k be k distinct elements of G and let b ₁, …, b _k be (not necessarily distinct) elements of G, where k is a positive integer smaller than the least prime divisor of |G|. We show that there is a permutation π on {1, …,k} such that a ₁ b _π(1), …, a _k b _π(k) are distinct, provided that any other prime divisor of |G| (if there is any) is greater than k!. This in particular confirms the Dasgupta-Károlyi-Serra-Szegedy conjecture for abelian p-groups. We also pose a new conjecture involving determinants and characters, and show that its validity implies Snevily’s conjecture for abelian groups of odd order. Our methods involve exterior algebras and characters.     

A proof of snevily’s conjecture

We prove Snevily’s conjecture, which states that for any positive integer k and any two k-element subsets {a ₁, …, a _k } and {b ₁, …, b _k } of a finite abelian group of odd order there exists a permutation π ∈ S _k such that all sums a _i + b _π(i) (i ∈ [1, k]) are pairwise distinct.     

Restricted sumsets and a conjecture of Lev

LetA, B, S be finite subsets of an abelian groupG. Suppose that the restricted sumsetC={α+b: α ∈A, b ∈B, and α − b ∉S} is nonempty and somec∈C can be written asa+b witha∈A andb∈B in at mostm ways. We show that ifG is torsion-free or elementary abelian, then |C|≥|A|+|B|−|S|−m. We also prove that |C|≥|A|+|B|−2|S|−m if the torsion subgroup ofG is cyclic. In the caseS={0} this provides an advance on a conjecture of Lev. This author is responsible for communications, and supported by the National Science Fund for Distinguished Young Scholars (No. 10425103) and the Key Program of NSF (No. 10331020) in China.     

A Neighborhood Condition for Graphs to Have [a, b]-Factors II

 Let a, b, m, and t be integers such that 1≤a<b and 1≤t≤⌉(b−m+1)/a⌉. Suppose that G is a graph of order |G| and H is any subgraph of G with the size |E(H)|=m. Then we prove that G has an [a,b]-factor containing all the edges of H if the minimum degree is at least a, |G|>((a+b)(t(a+b−1)−1)+2m)/b, and |N _G (x ₁)∪⋯ ∪N _G (x _t )|≥(a|G|+2m)/(a+b) for every independent set {x ₁,…,x _t }⊆V(G). This result is best possible in some sense and it is an extension of the result of H. Matsuda (A neighborhood condition for graphs to have [a,b]-factors, Discrete Mathematics 224 (2000) 289–292). Received: October, 2001 Final version received: September 17, 2002 RID="*" ID="*" This research was partially supported by the Ministry of Education, Science, Sports and Culture, Grant-in-Aid for Encouragement of Young Scientists, 13740084, 2001     

On a problem in additive number theory

For a set A, let P(A) be the set of all finite subset sums of A. We prove that if a sequence B={b ₁<b ₂<⋯} of integers satisfies b ₁≧11 and b _n+1≧3b _n +5 (n=1,2,…), then there exists a sequence of positive integers A={a ₁<a ₂<⋯} for which P(A)=ℕ∖B. On the other hand, if a sequence B={b ₁<b ₂<⋯} of positive integers satisfies either b ₁=10 or b ₂=3b ₁+4, then there is no sequence A of positive integers for which P(A)=ℕ∖B.     

On the Existence of Specific Stars in Planar Graphs

Given a graph G, a (k;a,b,c)-star in G is a subgraph isomorphic to a star K_1,3 with a central vertex of degree k and three leaves of degrees a, b and c in G. The main result of the paper is: Every planar graph G of minimum degree at least 3 contains a (k;a,b,c)-star with a≤ b≤ c and (i) k = 3, a≤ 10, or (ii) k = 4, a = 4, 4≤ b≤ 10, or (iii) k = 4, a = 5, 5≤ b≤ 9, or (iv) k = 4, 6≤ a≤ 7, 6≤ b≤ 8, or (v) k = 5, 4≤ a≤ 5, 5≤ b≤ 6 and 5≤ c≤ 7, or (vi) k = 5 and a = b = c = 6.     

The Erdős-Heilbronn problem in Abelian groups

Solving a problem of Erdős and Heilbronn, in 1994 Dias da Silva and Hamidoune proved that ifA is a set ofk residues modulo a primep,p≥2k−3, then the number of different elements of ℤ/pℤ that can be written in the forma+a′ wherea, a′ ∈A,a∈a′, is at least 2k−3. Here we extend this result to arbitrary Abelian groups in which the order of any nonzero element is at least 2k−3. Visiting the Rényi Institute of the Hungarian Academy of Sciences. Research partially supported by Hungarian Scientific Research Grants OTKA T043623 and T043631 and the CRM, University of Montreal.     

Distance graphs with maximum chromatic number

The distance graph G(D) has the set of integers as vertices and two vertices are adjacent in G(D) if their difference is contained in the set D⊂Z. A conjecture of Zhu states that if the chromatic number of G(D) achieves its maximum value |D|+1 then the graph has a triangle. The conjecture is proven to be true if |D|?3. We prove that the chromatic number of a distance graph with D={a,b,c,d} is five only if either D={1,2,3,4k} or D={a,b,a+b,b-a}. This confirms a stronger version of Zhu's conjecture for |D|=4, namely, if the chromatic number achieves its maximum value then the graph contains K₄.     

Gersgorin variations II: On themes of Fan and Gudkov

Assume F={f₁,. . .,f_n} is a family of nonnegative functions of n−1 nonnegative variables such that, for every matrix A of order n, |a_ii|>f_i (moduli of off-diagonal entries in row i of A) for all i implies A nonsingular. We show that there is a positive vector x, depending only on F, such that for all A=(a_ij), and all i, f_i≥∑_j|a_ij|{x_j}/x_i. This improves a theorem of Ky Fan, and yields a generalization of a nonsingularity criterion of Gudkov. Dedicated to Charles A. Micchelli, in celebration of his 60th birthday and our 30 years of friendship     

Disjoint homotopic paths and trees in a planar graph

In this paper we describe a polynomial-time algorithm for the following problem:given: a planar graphG embedded in ℝ², a subset {I ₁, …,I _p} of the faces ofG, and pathsC ₁, …,C _k inG, with endpoints on the boundary ofI ₁ ∪ … ∪I _p; find: pairwise disjoint simple pathsP ₁, …,P _k inG so that, for eachi=1, …,k, P _i is homotopic toC _i in the space ℝ²\(I ₁ ∪ … ∪I _p). Moreover, we prove a theorem characterizing the existence of a solution to this problem. Finally, we extend the algorithm to disjoint homotopic trees. As a corollary we derive that, for each fixedp, there exists a polynormial-time algorithm for the problem:given: a planar graphG embedded in ℝ² and pairwise disjoint setsW ₁, …,W _k of vertices, which can be covered by the boundaries of at mostp faces ofG;find: pairwise vertex-disjoint subtreesT ₁, …,T _k ofG whereT _i (i=1, …, k).     

On the Structure of Graphs with Bounded Asteroidal Number

 A set A⊆V of the vertices of a graph G=(V,E) is an asteroidal set if for each vertex a∈A, the set A\{a} is contained in one component of G−N[a]. The maximum cardinality of an asteroidal set of G, denoted by an (G), is said to be the asteroidal number of G. We investigate structural properties of graphs of bounded asteroidal number. For every k≥1, an (G)≤k if and only if an (H)≤k for every minimal triangulation H of G. A dominating target is a set D of vertices such that D∪S is a dominating set of G for every set S such that G[D∪S] is connected. We show that every graph G has a dominating target with at most an (G) vertices. Finally, a connected graph G has a spanning tree T such that d _T (x,y)−d _G (x,y)≤3·|D|−1 for every pair x,y of vertices and every dominating target D of G. Received: July 3, 1998 Final version received: August 10, 1999     

Non-<Emphasis Type="Italic">φ</Emphasis>-admissible normal subgroups of free burnside groups

In the present paper for arbitrary automorphism φ of the free Bunside group B(m, n) and for any odd number n ≥ 1003 a sufficient condition for existence of non-φ-admissible normal subgroup of B(m, n) was found. In particular, if automorphism φ is normal, then for any basis {a ₁, a ₂, …, a _m } of the group B(m, n) there is an integer k such that for each i the elements a _i and φ(a i) ^k are conjugates.     

Algebras whose equivalence relations are congruences

It is proved that all the equivalence relations of a universal algebra A are its congruences if and only if either |A| ≤ 2 or every operation f of the signature is a constant (i.e., f(a ₁ , . . . , a _n ) = c for some c ∈ A and all the a ₁ , . . . , a _n ∈ A) or a projection (i.e., f(a ₁ , . . . , a _n ) = a _i for some i and all the a ₁ , . . . , a _n ∈ A). All the equivalence relations of a groupoid G are its right congruences if and only if either |G| ≤ 2 or every element a ∈ G is a right unit or a generalized right zero (i.e., x _a  = y _a for all x, y ∈ G). All the equivalence relations of a semigroup S are right congruences if and only if either |S| ≤ 2 or S can be represented as S = A∪B, where A is an inflation of a right zero semigroup, and B is the empty set or a left zero semigroup, and ab = a, ba = a ² for a ∈ A, b ∈ B. If G is a groupoid of 4 or more elements and all the equivalence relations of it are right or left congruences, then either all the equivalence relations of the groupoid G are left congruences, or all of them are right congruences. A similar assertion for semigroups is valid without the restriction on the number of elements.     

Irreducible algebraic sets over divisible decomposed rigid groups

A soluble group G is said to be rigid if it contains a normal series of the form G = G ₁ > G ₂ > …> G _p > G _p+1 = 1, whose quotients G _i /G _i+1 are Abelian and are torsion-free when treated as right ℤ[G/G _i ]-modules. Free soluble groups are important examples of rigid groups. A rigid group G is divisible if elements of a quotient G _i /G _i+1 are divisible by nonzero elements of a ring ℤ[G/G _i ], or, in other words, G _i /G _i+1 is a vector space over a division ring Q(G/G _i ) of quotients of that ring. A rigid group G is decomposed if it splits into a semidirect product A ₁ A ₂…A _p of Abelian groups A _i ≅ G _i /G _i+1. A decomposed divisible rigid group is uniquely defined by cardinalities α _i of bases of suitable vector spaces A _i , and we denote it by M(α₁,…, α _p ). The concept of a rigid group appeared in [arXiv:0808.2932v1 [math.GR], ], where the dimension theory is constructed for algebraic geometry over finitely generated rigid groups. In [11], all rigid groups were proved to be equationally Noetherian, and it was stated that any rigid group is embedded in a suitable decomposed divisible rigid group M(α₁,…, α _p ). Our present goal is to derive important information directly about algebraic geometry over M(α₁,… α _p ). Namely, irreducible algebraic sets are characterized in the language of coordinate groups of these sets, and we describe groups that are universally equivalent over M(α₁,…, α _p ) using the language of equations.     

A variant of Davenport’s constant

Let p be a prime number. Let G be a finite abelian p-group of exponent n (written additively) and A be a non-empty subset of ]n[≔ {1, 2,…, n} such that elements of A are incongruent modulo p and non-zero modulo p. Let k ≥ D(G/|A| be any integer where D(G) denotes the well-known Davenport’s constant. In this article, we prove that for any sequence g ₁, g ₂,…, g _k (not necessarily distinct) in G, one can always extract a subsequence with 1 ≤ ℓ ≤ k such that

The Decomposition Dimension of Graphs

 For an ordered k-decomposition ? = {G ₁, G ₂,…,G _k } of a connected graph G and an edge e of G, the ?-representation of e is the k-tuple r(e|?) = (d(e, G ₁), d(e, G ₂),…,d(e, G _k )), where d(e, G _i ) is the distance from e to G _i . A decomposition ? is resolving if every two distinct edges of G have distinct representations. The minimum k for which G has a resolving k-decomposition is its decomposition dimension dec(G). It is shown that for every two positive integers k and n≥ 2, there exists a tree T of order n with dec(T) = k. It is also shown that dec(G) ≤n for every graph G of order n≥ 3 and that dec(K _n ) ≤⌊(2n + 5)/3⌋ for n≥ 3. Received: June 17, 1998 Final version received: August 10, 1999     

Graph Orientations with Edge-connection and Parity Constraints

Parity (matching theory) and connectivity (network flows) are two main branches of combinatorial optimization. In an attempt to understand better their interrelation, we study a problem where both parity and connectivity requirements are imposed. The main result is a characterization of undirected graphs G = (V,E) having a k-edge-connected T-odd orientation for every subset with |E| + |T| even. (T-odd orientation: the in-degree of v is odd precisely if v is in T.) As a corollary, we obtain that every (2k)-edge-connected graph with |V| + |E| even has a (k-1)-edge-connected orientation in which the in-degree of every node is odd. Along the way, a structural characterization will be given for digraphs with a root-node s having k edge-disjoint paths from s to every node and k-1 edge-disjoint paths from every node to s. Received December 14, 1998/Revised January 12, 2001 RID="*" ID="*" Supported by the Hungarian National Foundation for Scientific Research, OTKA T029772. Part of research was done while this author was visiting EPFL, Lausanne, June, 1998. RID="†" ID="†" Supported by the Hungarian National Foundation for Scientific Research, OTKA T029772 and OTKA T030059.     

Cycles in bipartite graphs

For k an integer, let G(a, b, k) denote a simple bipartite graph with bipartition (A, B) where |A| = a ≥ 2, |B| = b ≥ k ≥ 2, and each vertex of A has degree at least k. We prove two results concerning the existence of cycles in G(a, b, k).