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.     

Transversals of additive Latin squares

LetA={a ₁, …,a _k} andB={b ₁, …,b _k} be two subsets of an Abelian groupG, k≤|G|. Snevily conjectured that, whenG is of odd order, there is a permutationπ ∈S _ksuch that the sums α _i +b _i , 1≤i≤k, are pairwise different. Alon showed that the conjecture is true for groups of prime order, even whenA is a sequence ofk<|G| elements, i.e., by allowing repeated elements inA. In this last sense the result does not hold for other Abelian groups. With a new kind of application of the polynomial method in various finite and infinite fields we extend Alon’s result to the groups (ℤ _p ) ^a and in the casek<p, and verify Snevily’s conjecture for every cyclic group of odd order. Supported by Hungarian research grants OTKA F030822 and T029759. Supported by the Catalan Research Council under grant 1998SGR00119. Partially supported by the Hungarian Research Foundation (OTKA), grant no. T029132.     

Successions in integer partitions

A partition of an integer n is a representation n=a ₁+a ₂+⋅⋅⋅+a _k , with integer parts 1≤a ₁≤a ₂≤…≤a _k . For any fixed positive integer p, a p-succession in a partition is defined to be a pair of adjacent parts such that a _i+1−a _i =p. We find generating functions for the number of partitions of n with no p-successions, as well as for the total number of such successions taken over all partitions of n. In the process, various interesting partition identities are derived. In addition, the Hardy-Ramanujan asymptotic formula for the number of partitions is used to obtain an asymptotic estimate for the average number of p-successions in the partitions of n. This material is based upon work supported by the National Research Foundation under grant number 2053740.     

Centralizers of coprime automorphisms of finite groups

Let A be an elementary abelian group of order p ^k with k ≥ 3 acting on a finite p′-group G. The following results are proved. If γ _k-2(C _G (a)) is nilpotent of class at most c for any ${a \in A^{\#}}$ , then γ _k-2(G) is nilpotent and has {c, k, p}-bounded nilpotency class. If, for some integer d such that 2 ^d  + 2 ≤ k, the dth derived group of C _G (a) is nilpotent of class at most c for any ${a \in A^{\#}}$ , then the dth derived group G ^(d) is nilpotent and has {c, k, p}-bounded nilpotency class.     

Omega subgroups of pro-<Emphasis Type="Italic">p</Emphasis> groups

Let G be a pro-p group and let k ≥ 1. If γ _k(p−1) (G) ≤ γ _r for some r and s such that k(p − 1) < r + s(p − 1), we prove that the exponent of Ω_i(G) is at most p ^i+k−1 for all i. Supported by the Spanish Ministry of Science and Education, grant MTM2004-04665, partly with FEDER funds. The first author is also supported by the University of the Basque Country, grant UPV05/99. The second author is also supported by the Basque Government.     

Asymptotic Upper Bounds for Ramsey Functions

 We show that for any graph G with N vertices and average degree d, if the average degree of any neighborhood induced subgraph is at most a, then the independence number of G is at least Nf _{a +1}(d), where f _{a +1}(d)=∫₀ ¹(((1−t)^{1/( a +1)})/(a+1+(d−a−1)t))dt. Based on this result, we prove that for any fixed k and l, there holds r(K _k + _l ,K _n )≤ (l+o(1))n ^k /(logn) ^{k −1}. In particular, r(K _k , K _n )≤(1+o(1))n ^{k −1}/(log n) ^{k −2}. Received: May 11, 1998 Final version received: March 24, 1999     

Privileged users in zero-error transmission over a noisy channel

The k-th power of a graph G is the graph whose vertex set is V(G) ^k , where two distinct k-tuples are adjacent iff they are equal or adjacent in G in each coordinate. The Shannon capacity of G, c(G), is lim _k→∞ α(G ^k )^1/k , where α(G) denotes the independence number of G. When G is the characteristic graph of a channel C, c(G) measures the effective alphabet size of C in a zero-error protocol. A sum of channels, C = Σ _i C _i , describes a setting when there are t ≥ 2 senders, each with his own channel C _i , and each letter in a word can be selected from any of the channels. This corresponds to a disjoint union of the characteristic graphs, G = Σ _i G _i . It is well known that c(G) ≥ Σ _i c(G _i ), and in [1] it is shown that in fact c(G) can be larger than any fixed power of the above sum. We extend the ideas of [1] and show that for every F, a family of subsets of [t], it is possible to assign a channel C _i to each sender i ∈ [t], such that the capacity of a group of senders X ⊂ [t] is high iff X contains some F ∈ F. This corresponds to a case where only privileged subsets of senders are allowed to transmit in a high rate. For instance, as an analogue to secret sharing, it is possible to ensure that whenever at least k senders combine their channels, they obtain a high capacity, however every group of k − 1 senders has a low capacity (and yet is not totally denied of service). In the process, we obtain an explicit Ramsey construction of an edge-coloring of the complete graph on n vertices by t colors, where every induced subgraph on exp vertices contains all t colors. Research supported in part by a USA-Israeli BSF grant, by the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. Research partially supported by a Charles Clore Foundation Fellowship.     

Locally Closed Semirings

 We call a semiring S locally closed if for all a ∈ S there is some integer k such that 1 + a + ⋯ + a ^k  =1 + a + ⋯ + a ^k + 1 . In any locally closed semiring we may define a star operation a ↦ a ^*, where a ^* is the above finite sum. We prove that when S is locally closed and commutative, then S is an iteration semiring. Partially supported by grant no. T30511 from the National Foundation of Hungary for Scientific Research and the Austrian–Hungarian Bilateral Research and Development Fund, no. A-4/1999, and by the Austrian–Hungarian Action Foundation. Partially supported by the Austrian–Hungarian Bilateral Research and Development Fund, no. A-4/1999, and by the Austrian–Hungarian Action Foundation. Received March 16, 2001     

On Some Three-Color Ramsey Numbers

 In this paper we study three-color Ramsey numbers. Let K _i,j denote a complete i by j bipartite graph. We shall show that (i) for any connected graphs G ₁, G ₂ and G ₃, if r(G ₁, G ₂)≥s(G ₃), then r(G ₁, G ₂, G ₃)≥(r(G ₁, G ₂)−1)(χ(G ₃)−1)+s(G ₃), where s(G ₃) is the chromatic surplus of G ₃; (ii) (k+m−2)(n−1)+1≤r(K _1,k , K _1,m , K _n )≤ (k+m−1)(n−1)+1, and if k or m is odd, the second inequality becomes an equality; (iii) for any fixed m≥k≥2, there is a constant c such that r(K _k,m , K _k,m , K _n )≤c(n/logn), and r(C _2m , C _2m , K _n )≤c(n/logn) ^m/(m−1) for sufficiently large n. Received: July 25, 2000 Final version received: July 30, 2002 RID="*" ID="*" Partially supported by RGC, Hong Kong; FRG, Hong Kong Baptist University; and by NSFC, the scientific foundations of education ministry of China, and the foundations of Jiangsu Province Acknowledgments. The authors are grateful to the referee for his valuable comments. AMS 2000 MSC: 05C55     

An optimal version of an inequality involving the third symmetric means

Let (GA) _n ^[k](a), A _n (a), G _n (a) be the third symmetric mean of k degree, the arithmetic and geometric means of a ₁, …, a _n (a _i > 0, i = 1, …, n), respectively. By means of descending dimension method, we prove that the maximum of p is k−1/n−1 and the minimum of q is n/n−1(k−1/k) ^k/n so that the inequalities {fx505-1} hold.     

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).     

Oscillatory solutions of nonhomogeneous linear differential equations

The complex oscillation of nonhomogeneous linear differential equations with transcendental coefficients is discussed. Results concerning the equation f ^(k)+a _k−1 f ^(k−1)+...+a ₀ f=F where a ₀,...,a _k−i and Fare entire functions, possessing an oscillatory solution subspace in which all solutions (with at most one exception) have infinite exponent of convergence of zeros are obtained. All solutions of the equation are also characterized when the coefficients a ₀,a ₁,...,a _k−1 are polynomials and F=h exp (p ₀), where p ₀ is a polynomial and h is an entire function. Author supported by Max-Planck-Gesellschaft and by NSFC.     

On thek dimensional Piatetski-Shapiro prime number theorem

Thek-dimensional Piatetski-Shapiro prime number problem fork⩾3 is studied. Let π(x ₁ c ₁,⋯,c _k ) denote the number of primesp withp⩽x, , where 1<c ₁<⋯<c _k are fixed constants. It is proved that π(x;c ₁,⋯,c _k ) has an asymptotic formula ifc ₁ ⁻¹ +⋯+c _k ⁻¹ >k−k/(4k ²+2). Project supported by the National Natural Science Foundation of China (Grant No. 19801021) and the Natural Science Foundation of Shandong Province (Grant No.Q98A02110).     

On exactlym times covers

In this paper it is shown that if every integer is covered bya ₁+n ₁ℤ,…,a _k +n _k ℤ exactlym times then for eachn=1,…,m there exist at least ( _n ^m ) subsetsI of {1,…k} such that ∑ _{i ∈ I} 1/n _i equalsn. The bound ( _n ^m ) is best possible. Research supported by the National Nature Science Foundation of P.R. of China.     

Almost poised basic hypergeometric series

Given a basic hypergeometric series with numerator parametersa ₁,a ₂, ...,a _r and denominator parametersb ₂, ...,b _r, we say it isalmost poised ifb _i, =a ₁ q ^δ,i a _i,δ_i = 0, 1 or 2, for 2 ≤i ≤r. Identities are given for almost poised series withr = 3 andr = 5 when a₁, =q ⁻²ⁿ. Partially supported by N.S.F. Grant No. DMS-8521580.     

The intersection of subgroups of finite <Emphasis Type="Italic">p</Emphasis>-groups

For a finite p-group G and a positive integer k let I _k (G) denote the intersection of all subgroups of G of order p ^k . This paper classifies the finite p-groups G with I_k(G) @ C_p^k-1{{I}_k(G)\cong C_{p^{k-1}}} for primes p > 2. We also show that for any k, α ≥ 0 with 2(α + 1) ≤ k ≤ n−α the groups G of order p ⁿ with I_k(G) @ C_p^k-a{{I}_k(G)\cong C_{p^{k-\alpha}}} are exactly the groups of exponent p ^n-α .     

Selection in Monotone Matrices and Computingkth Nearest Neighbors

Anm×nmatrix =(a_{i, j}), 1≤i≤mand 1≤j≤n, is called atotally monotonematrix if for alli₁, i₂, j₁, j₂, satisfying 1≤i₁<i₂≤m, 1≤j₁<j₂≤n.[formula]We present an[formula]time algorithm to select thekth smallest item from anm×ntotally monotone matrix for anyk≤mn. This is the first subquadratic algorithm for selecting an item from a totally monotone matrix. Our method also yields an algorithm of the same time complexity for ageneralized row-selection problemin monotone matrices. Given a setS={p₁,…, p_n} ofnpoints in convex position and a vectork={k₁,…, k_n}, we also present anO(n^4/3log^c n) algorithm to compute thek_ith nearest neighbor ofp_ifor everyi≤n; herecis an appropriate constant. This algorithm is considerably faster than the one based on a row-selection algorithm for monotone matrices. If the points ofSare arbitrary, then thek_ith nearest neighbor ofp_i, for alli≤n, can be computed in timeO(n^7/5 log^c n), which also improves upon the previously best-known result.     

The Existence of （v, 4, 1） Disjoint Difference Families with v a Prime Power

A （v, k, λ） difference family （（v, k, λ）-DF in short） over an abelian group G of order v, is a collection F=（Bi｜i ∈ I} of k-subsets of G, called base blocks, such that any nonzero element of G can be represented in precisely A ways as a difference of two elements lying in some base blocks in F. A （v, k, λ）-DDF is a difference family with disjoint blocks. In this paper, by using Weil＇s theorem on character sum estimates, it is proved that there exists a （p^n, 4, 1）-DDF, where p = 1 （rood 12） is a prime number and n ≥1.     

OD-characterization of Almost Simple Groups Related to U3（5）

Let G be a finite group with order ｜G｜=p1^α1p2^α2……pk^αk, where p1 〈 p2 〈……〈 Pk are prime numbers. One of the well-known simple graphs associated with G is the prime graph （or Gruenberg- Kegel graph） denoted .by г（G） （or GK（G））. This graph is constructed as follows： The vertex set of it is π（G） = {p1,p2,…,pk} and two vertices pi, pj with i≠j are adjacent by an edge （and we write pi - pj） if and only if G contains an element of order pipj. The degree deg（pi） of a vertex pj ∈π（G） is the number of edges incident on pi. We define D（G） ：= （deg（p1）, deg（p2）,..., deg（pk））, which is called the degree pattern of G. A group G is called k-fold OD-characterizable if there exist exactly k non- isomorphic groups H such that ｜H｜ = ｜G｜ and D（H） = D（G）. Moreover, a 1-fold OD-characterizable group is simply called OD-characterizable. Let L ：= U3（5） be the projective special unitary group. In this paper, we classify groups with the same order and degree pattern as an almost simple group related to L. In fact, we obtain that L and L.2 are OD-characterizable; L.3 is 3-fold OD-characterizable; L.S3 is 6-fold OD-characterizable.     

Graph decompositions without isolated vertices III

Let G be a graph of order n, and n = Σ^k_i=1 a_i be a partition of n with a_i ≥ 2. In this article we show that if the minimum degree of G is at least 3k−2, then for any distinct k vertices v₁,…, v_k of G, the vertex set V(G) can be decomposed into k disjoint subsets A₁,…, A_k so that |A_i| = a_i,v_iisA_i is an element of A_i and “the subgraph induced by A_i contains no isolated vertices” for all i, 1 ≥ i ≥ k. Here, the bound on the minimum degree is sharp. © 1997 John Wiley & Sons, Inc.