共查询到20条相似文献,搜索用时 46 毫秒
1.
LetA={a
1, …,a
k} and {b
1, …,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. 相似文献
2.
Noga Alon 《Israel Journal of Mathematics》2000,117(1):125-130
We prove that for every odd primep, everyk≤p
and every two subsets
A={a
1, …,a
k
} andB={b
1, …,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. 相似文献
3.
Let G be a finite abelian group with |G| > 1. Let a
1, …, a
k
be k distinct elements of G and let b
1, …, 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
1
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. 相似文献
4.
Bodan Arsovski 《Israel Journal of Mathematics》2011,182(1):505-508
We prove Snevily’s conjecture, which states that for any positive integer k and any two k-element subsets {a
1, …, a
k
} and {b
1, …, 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. 相似文献
5.
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. 相似文献
6.
Haruhide Matsuda 《Graphs and Combinatorics》2002,18(4):763-768
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
1)∪⋯ ∪N
G
(x
t
)|≥(a|G|+2m)/(a+b) for every independent set {x
1,…,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 相似文献
7.
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
1<b
2<⋯} of integers satisfies b
1≧11 and b
n+1≧3b
n
+5 (n=1,2,…), then there exists a sequence of positive integers A={a
1<a
2<⋯} for which P(A)=ℕ∖B. On the other hand, if a sequence B={b
1<b
2<⋯} of positive integers satisfies either b
1=10 or b
2=3b
1+4, then there is no sequence A of positive integers for which P(A)=ℕ∖B. 相似文献
8.
Given a graph G, a (k;a,b,c)-star in G is a subgraph isomorphic to a star K1,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. 相似文献
9.
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. 相似文献
10.
Javier Barajas 《Discrete Mathematics》2008,308(8):1355-1365
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 K4. 相似文献
11.
Alan J. Hoffman 《Advances in Computational Mathematics》2006,25(1-3):1-6
Assume F={f1,. . .,fn} is a family of nonnegative functions of n−1 nonnegative variables such that, for every matrix A of order n, |aii|>fi (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=(aij), and all i, fi≥∑j|aij|{xj}/xi. 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 相似文献
12.
A. Schrijver 《Discrete and Computational Geometry》1991,6(1):527-574
In this paper we describe a polynomial-time algorithm for the following problem:given: a planar graphG embedded in ℝ2, a subset {I
1, …,I
p} of the faces ofG, and pathsC
1, …,C
k inG, with endpoints on the boundary ofI
1 ∪ … ∪I
p; find: pairwise disjoint simple pathsP
1, …,P
k inG so that, for eachi=1, …,k, P
i is homotopic toC
i in the space ℝ2\(I
1 ∪ … ∪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 ℝ2 and pairwise disjoint setsW
1, …,W
k of vertices, which can be covered by the boundaries of at mostp faces ofG;find: pairwise vertex-disjoint subtreesT
1, …,T
k ofG whereT
i
(i=1, …, k). 相似文献
13.
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 相似文献
14.
V. S. Atabekyan 《Journal of Contemporary Mathematical Analysis (Armenian Academy of Sciences)》2010,45(2):112-122
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
1, a
2, …, 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. 相似文献
15.
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
1
, . . . , a
n
) = c for some c ∈ A and all the a
1
, . . . , a
n
∈ A) or a projection (i.e., f(a
1
, . . . , a
n
) = a
i
for some i and all the a
1
, . . . , 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
2 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. 相似文献
16.
N. S. Romanovskii 《Algebra and Logic》2009,48(6):449-464
A soluble group G is said to be rigid if it contains a normal series of the form G = G
1 > G
2 > …> 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
1
A
2…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(α1,…, α
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(α1,…, α
p
). Our present goal is to derive important information directly about algebraic geometry over M(α1,… α
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(α1,…, α
p
) using the language of equations. 相似文献
17.
A variant of Davenport’s constant 总被引:1,自引:1,他引:0
R. Thangadurai 《Proceedings Mathematical Sciences》2007,117(2):147-158
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
1, g
2,…, g
k
(not necessarily distinct) in G, one can always extract a subsequence with 1 ≤ ℓ ≤ k such that
where a
j
∈ A for all j. We provide examples where this bound cannot be improved. Furthermore, for the cyclic groups, we prove some sharp results
in this direction. In the last section, we explore the relation between this problem and a similar problem with prescribed
length. The proof of Theorem 1 uses group-algebra techniques, while for the other theorems, we use elementary number theory
techniques. 相似文献
18.
For an ordered k-decomposition ? = {G
1, G
2,…,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
1), d(e, G
2),…,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 相似文献
19.
Graph Orientations with Edge-connection and Parity Constraints 总被引:2,自引:0,他引:2
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. 相似文献
20.
Bill Jackson 《Journal of Combinatorial Theory, Series B》1981,30(3):332-342
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). 相似文献