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.     

Analogues of Horn’s theorem for finite unions of starshaped sets in ℝ<Superscript><Emphasis Type="Italic">d</Emphasis></Superscript>

Fix k, d, 1 ≤ k ≤ d + 1. Let $ \mathcal{F} $ \mathcal{F} be a nonempty, finite family of closed sets in ℝ ^d , and let L be a (d − k + 1)-dimensional flat in ℝ ^d . The following results hold for the set T ≡ ∪{F: F in $ \mathcal{F} $ \mathcal{F} }. Assume that, for every k (not necessarily distinct) members F ₁, …, F _k of $ \mathcal{F} $ \mathcal{F} ,∪{F _i : 1 ≤ i ≤ k} is starshaped and the corresponding kernel contains a translate of L. Then T is starshaped, and its kernel also contains a translate of L.     

Independent Trees and Branchings in Planar Multigraphs

 The following statement is proved: Let G be a finite directed or undirected planar multigraph and s be a vertex of G such that for each vertex x≠s of G, there are at least k pairwise openly disjoint paths in G from x to s where k∉{3,4,5} if G is directed. Then there exist k spanning trees T ₁, … ,T _k in G directed towards s if G is directed such that for each vertex x≠s of G, the k paths from x to s in T ₁, … ,T _k are pairwise openly disjoint. – The case where G is directed and k∈{3,4,5} remains open. Received: January 30, 1995 / Revised: October 7, 1996     

Highly parity linked graphs

A graph G is k-linked if G has at least 2k vertices, and for any 2k vertices x ₁,x ₂, …, x _k ,y ₁,y ₂, …, y _k , G contains k pairwise disjoint paths P ₁, …, P _k such that P _i joins x _i and y _i for i = 1,2, …, k. We say that G is parity-k-linked if G is k-linked and, in addition, the paths P ₁, …, P _k can be chosen such that the parities of their length are prescribed. Thomassen [22] was the first to prove the existence of a function f(k) such that every f(k)-connected graph is parity-k-linked if the deletion of any 4k-3 vertices leaves a nonbipartite graph. In this paper, we will show that the above statement is still valid for 50k-connected graphs. This is the first result that connectivity which is a linear function of k guarantees the Erdős-Pósa type result for parity-k-linked graphs. Research partly supported by the Japan Society for the Promotion of Science for Young Scientists, by Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research and by Inoue Research Award for Young Scientists.     

The classification of complete orientable 2-dimensional area-minimizing mod 2 surfaces in ℝn

Let S ⊂ ℝⁿ be a complete 2-dimensional areaminimizing mod 2 surface. Then S = x₁ (M₁) ∪ … ∪ x_r (M_r) where each M_j is connected, x_j: M_j → V_j is a classical minimal immersion into an affine subspace V_j of ℝⁿ, and the subspaces V₁,…, V_r are pairwise orthogonal. Here we prove that if M_j is orientable, then x_j (M_j) is either aflat plane or, in suitable coordinates, a generalized complex hyperbola.     

On J. H. C. Whitehead's aspherical question I

A connected, finite two-dimensional CW-complex with fundamental group isomorphic toG is called a [G, 2] _f -complex. LetL⊲G be a normal subgroup ofG. L has weightk if and only ifk is the smallest integer such that there exists {l ₁,…,l _k}⊆L such thatL is the normal closure inG of {l ₁,…,l _k}. We prove that a [G, 2] _f -complexX may be embedded as a subcomplex of an aspherical complexY=X∪{e ₁ ² ,…,e _k ² } if and only ifG has a normal subgroupL of weightk such thatH=G/L is at most two-dimensional and defG=defH+k. Also, ifX is anon-aspherical [G, 2] _f -subcomplex of an aspherical 2-complex, then there exists a non-trivial superperfect normal subgroupP such thatG/P has cohomological dimension ≤2. In this case, any torsion inG must be inP.     

Degree Sums and Path-Factors in Graphs

 Let G be a connected graph of order n and suppose that n=∑ _{i =1} ^k n _i , where n _i ≥2 are integers. In this paper we give some sufficient conditions in terms of degree sums to ensure that G contains a spanning subgraph consisting of vertex disjoint paths of orders n ₁,n ₂,…,n _k . Received: June 30, 1999 Final version received: July 31, 2000     

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.     

Absorbing Angles,Steiner Minimal Trees,and Antipodality

We give a new proof that a star {op _i :i=1,…,k} in a normed plane is a Steiner minimal tree of vertices {o,p ₁,…,p _k } if and only if all angles formed by the edges at o are absorbing (Swanepoel in Networks 36: 104–113, 2000). The proof is simpler and yet more conceptual than the original one. We also find a new sufficient condition for higher-dimensional normed spaces to share this characterization. In particular, a star {op _i :i=1,…,k} in any CL-space is a Steiner minimal tree of vertices {o,p ₁,…,p _k } if and only if all angles are absorbing, which in turn holds if and only if all distances between the normalizations \frac1||p_i||p_i\frac{1}{\Vert p_{i}\Vert}p_{i} equal 2. CL-spaces include the mixed ℓ ₁ and ℓ _∞ sum of finitely many copies of ℝ.     

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.     

An application of ergodic theory to a problem in geometric ramsey theory

LetE be a measurable subset of ℝ ^k ,k>2, with XXX(E)>0. LetV = {0,υ ₁, …,υ _k+1} ε ℝ ^k , whereυ ₁, …,υ _k+1 are affinely independent. We show that forr large enough, we can find an isometric copy ofrV arbitrarily close toE. This is a generalization of a theorem of Furstenberg, Katznelson and Weiss [FKW] showing a similar property for ℝ²,V = {0,υ ₁,υ ₂}.     

The Erdös-Jacobson-Lehel conjecture on potentiallyP k-graphic sequence is true

A variation in the classical Turan extrernal problem is studied. A simple graphG of ordern is said to have propertyPk if it contains a clique of sizek+1 as its subgraph. Ann-term nonincreasing nonnegative integer sequence π=(d₁, d₂,⋯, d₂) is said to be graphic if it is the degree sequence of a simple graphG of ordern and such a graphG is referred to as a realization of π. A graphic sequence π is said to be potentiallyP _k-graphic if it has a realizationG having propertyP _k . The problem: determine the smallest positive even number σ(k, n) such that everyn-term graphic sequence π=(d₁, d₂,…, d₂) without zero terms and with degree sum σ(π)=(d ₁+d ₂+ …+d ₂) at least σ(k,n) is potentially P_k-graphic has been proved positive. Project supported by the National Natural Science Foundation of China (Grant No. 19671077) and the Doctoral Program Foundation of National Education Department of China.     

On Projections of Semi-Algebraic Sets Defined by Few Quadratic Inequalities

Let S⊂ℝ ^k+m be a compact semi-algebraic set defined by P ₁≥0,…,P _ℓ ≥0, where P _i ∈ℝ[X ₁,…,X _k ,Y ₁,…,Y _m ], and deg (P _i )≤2, 1≤i≤ℓ. Let π denote the standard projection from ℝ ^k+m onto ℝ ^m . We prove that for any q>0, the sum of the first q Betti numbers of π(S) is bounded by (k+m) ^{O(q ℓ)}. We also present an algorithm for computing the first q Betti numbers of π(S), whose complexity is . For fixed q and ℓ, both the bounds are polynomial in k+m. The author was supported in part by an NSF Career Award 0133597 and a Sloan Foundation Fellowship.     

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.     

Deformation of certain quadratic algebras and the corresponding quantum semigroups

LetV be a finite-dimensional vector space. Given a decompositionV⊗V=⊕ _i=1,…n I _i , definen quadratic algebrasQ(V, J _(m)) whereJ _(m)=⊕ _i≠m I _i . There is also a quantum semigroupM(V; I ₁, …,I _n ) which acts on all these quadratic algebras. The decomposition determines as well a family of associative subalgebras of End (V ^⊗k ), which we denote byA _k =A _k (I ₁,…,I _n ),k≥2. In the classical case, whenV⊗V decomposes into the symmetric and skewsymmetric tensors,A _k coincides with the image of the representation of the group algebra of the symmetric groupS _k in End(V ^⊗k ). LetI _i,h be deformations of the subspacesI _i . In this paper we give a criteria for flatness of the corresponding deformations of the quadratic algebrasQ(V, J _(m),h ) and the quantum semigroupM(V;I _1,h ,…,I _n,h ). It says that the deformations will be flat if the algebrasA _k (I ₁, …,I _n ) are semisimple and under the deformation their dimension does not change. Usually, the decomposition intoI _i is defined by a given semisimple operatorS onV⊗V, for whichI _i are its eigensubspaces, and the deformationsI _i,h are defined by a deformationS _h ofS. We consider the cases whenS _h is a deformation of Hecke or Birman-Wenzl symmetry, and also the case whenS _h is the Yang-Baxter operator which appears by a representation of the Drinfeld-Jimbo quantum group. Applying the flatness criteria we prove that in all these cases we obtain flat deformations of the quadratic algebras and the corresponding quantum semigroups. Partially supported by a grant from the Israel Science Foundation administered by the Israel Academy of Sciences.     

Large antipodal families

A family {A _i | i ∈ I} of sets in ℝ ^d is antipodal if for any distinct i, j ∈ I and any p ∈ A _i , q ∈ A _j , there is a linear functional ϕ:ℝ ^d → ℝ such that ϕ(p) ≠ ϕ(q) and ϕ(p) ≤ ϕ(r) ≤ ϕ(q) for all r ∈ ∪ _i∈I A _i . We study the existence of antipodal families of large finite or infinite sets in ℝ³. The research was supported by the Hungarian-South African Intergovernmental Scientific and Technological Cooperation Programme, NKTH Grant no. ZA-21/2006 and South African National Research Foundation Grant no. UID 61853, as well as Hungarian National Foundation for Scientific Research Grants no. NK 67867, no. T47102, and no. K72537.     

Graphs whose every transitive orientation contains almost every relation

Given a graphG onn vertices and a total ordering ≺ ofV(G), the transitive orientation ofG associated with ≺, denotedP(G; ≺), is the partial order onV(G) defined by settingx<y inP(G; ≺) if there is a pathx=x ₁ x ₂…x _r=y inG such thatx ₁ ≺x _j for 1≦i<j≦r. We investigate graphsG such that every transitive orientation ofG contains ₂ ⁿ −o(n ²) relations. We prove that almost everyG _n,p satisfies this requirement if , but almost noG _n,p satisfies the condition if (pn log log logn)/(logn log logn) is bounded. We also show that every graphG withn vertices and at mostcn logn edges has some transitive orientation with fewer than ₂ ⁿ −δ(c)n ² relations. Partially supported by MCS Grant 8104854.     

Polynomials hardly commuting with increasing bijections

Let I be an interval in the real line ℝ. Among the real polynomials that take I to I, we ask which ones do not commute with any increasing bijection of I other than identity. For this purely algebraic problem, the solution involves concepts in topological dynamics. Our main characterizations are in terms of full orbits of critical points and periodic points. Using these, we obtain simpler criterion, namely, that for no nontrivial subinterval K⊂I, the successive images {f ⁿ (K):n=0,1,2,…} form a pairwise disjoint collection. This problem is of interest in topological dynamics because it is about characterization of polynomials with unique self-topological-conjugacy.