Estimates related to sumfree subsets of sets of integers

A subsetA of the positive integers ?₊ is called sumfree provided (A+A)∩A=ø. It is shown that any finite subsetB of ?₊ contains a sumfree subsetA such that |A|≥1/3(|B|+2), which is a slight improvement of earlier results of P. Erdös [Erd] and N. Alon-D. Kleitman [A-K]. The method used is harmonic analysis, refining the original approach of Erdös. In general, defines _k (B) as the maximum size of ak-sumfree subsetA ofB, i.e. (A) _k = $\underbrace {A + ... + A}_{k times}$ % MathType!End!2!1! is disjoint fromA. Elaborating the techniques permits one to prove that, for instance, $s_3 \left( B \right) > \frac{{\left| B \right|}}{4} + c\frac{{\log \left| B \right|}}{{\log \log \left| B \right|}}$ % MathType!End!2!1!as an improvement of the estimate $s_k \left( B \right) > \frac{{\left| B \right|}}{4}$ % MathType!End!2!1! resulting from Erdös’ argument. It is also shown that in an inequalitys _k (B)>δ _k |B|, valid for any finite subsetB of ?₊, necessarilyδ _k → 0 fork → ∞ (which seemed to be an unclear issue). The most interesting part of the paper are the methods we believe and the resulting harmonic analysis questions. They may be worthwhile to pursue.     

On the growth of algebras with bialgebra action

Ifk is a field,A ak-algebra, andB ak-bialgebra which acts onA, we study the rate of growth ofA under its algebra structure together with the action ofB. We then briefly place our results in the more general context of a vector spaceA on which anoperad acts, and sketch an application to a (still open) question on finitely generated subalgebras of free associative algebras. Dedicated to the memory of Shimshon Amitsur 1991Mathematics Subject Classifications: Primary: 11N45, 16P90, 16W30; secondary: 08B20, 08C15, 11P99, 13N99, 17A01. Work done while the author held NSF contract DMS 93-03379. An erratum to this article is available at .     

Über Deformationen von analytischen Abbildungskeimen

The notion of deformations of germs of k-analytic mappings generalizes the one of deformations of germs of k-analytic spaces. Using algebraic terms, we prove:

1. The morphism f: A→B of analytic algebras is rigid, iff it is infinitesimally rigid. Moreover, this is equivalent to Ex_A (B,B)=0. This theorem generalizes a result of SCHUSTER [11].
2. Let A be a regular analytic algebra. Then f is rigid iff there exists a rigid analytic algebra B_o such that f is equivalent to the canonic injection A→A?B_o.
3. If f is “almost everywhere” rigid or smooth, then the injection Ext _B ^l (Ω_B|A, Bⁿ)→Ex_A(B, Bⁿ) is an isomorphism.

     

On Erdos' ten-point problem

Around 1994, Erdoset al. abstracted from their work the following problem: “Given ten pointsA _ij, 1≤i≤j≤5, on a plane and no three of them being collinear, if there are five pointsA _k, 1≤k≤5, on the plane, including points at infinity, with at least two points distinct, such thatA _i, A_j, A_ij are collinear, where 1≤i≤j≤5, is it true that there are only finitely many suchA _k's?” Erdoset al. obtained the result that generally there are at most 49 groups of suchA _k's. In this paper, using Clifford algebra and Wu's method, we obtain the results that generally there are at most 6 such groups ofA _k's.     

On k-Subspaces of L-vector-spaces

Let k ? L be division rings, with [L: k]_right <∞ and let B_k ? A_L be right vector spaces. Conditions are established in terms of the k-codimension of B in A, respectively the k-dimension of B, for there to exist a nonzero element a∈A such that aL∪B={0}, respectively an L-linear functional f on A such that f(B). Some consequences and related open questions are discussed.     

Graph decompositions without isolates

A. Frank (Problem session of the Fifth British Combinatorial Conference, Aberdeen, Scotland, 1975) conjectured that if G = (V, E) is a connected graph with all valencies ≥k and a₁,…,a_k ≥ 2 are integers with Σ a_i = |V |, then V may be decomposed into subsets A₁,…,A_k so that |A_i | = a_i and the subgraph spanned by A_i in G has no isolated vertices (i = 1,…,k). The case k = 2 is proved in Maurer (J. Combin. Theory Ser. B27 (1979), 294–319) along with some extensions. The conjecture for k = 3 and a result stronger than Maurer's extension for k = 2 are proved. A related characterization of a k-connected graph is also included in the paper, and a proof of the conjecture for the case a₁ = a₂ = … = a_k?1 = 2.     

Geometric progressions in sumsets over finite fields

Given two sets A, B í \Bbb F_q^d{\cal A}, {\cal B}\subseteq {\Bbb F}_q^d , the set of d dimensional vectors over the finite field \Bbb F_q{\Bbb F}_q with q elements, we show that the sumset A+B = {a+b | a ? A, b ? B}{\cal A}+{\cal B} = \{{\bf a}+{\bf b}\ \vert\ {\bf a} \in {\cal A}, {\bf b} \in {\cal B}\} contains a geometric progression of length k of the form vΛ ^j , where j = 0,…, k − 1, with a nonzero vector v ? \Bbb F_q^d{\bf v} \in {\Bbb F}_q^d and a nonsingular d × d matrix Λ whenever # A # B 3 20 q^2d-2/k\# {\cal A} \# {\cal B} \ge 20 q^{2d-2/k} . We also consider some modifications of this problem including the question of the existence of elements of sumsets on algebraic varieties.     

Optimal threat strategies of bimatrix games

A bi-matrix threat game is defined as a triple (A,B,S) whereA andB arem×n payoff matrices, andS is a closed convex subset of the plane, with (a _ij,B _ij) εS for eachi,j. Given (threat) mixed strategiesx andy,Nash's model suggests that the eventual outcome will be that point (u, v) εS which maximizes the product (u ?xAy ^t) (v ?xBy ^t) subject tou ≥xAy ^t,v ≥xBy ^t. Optimality of the threat strategies is then defined in the obvious way. A constructive proof of existence of optimal threat strategies is given; in particular, it is shown that they are optimal strategies for the matrix gameA-kB, wherek is to be determined. In this paper,k is approximated by aNewton-Raphson technique. Two examples are solved in detail.     

Probabilistic constructions of B 2[g] sequences

We use the probabilistic method to prove that for any positive integer g there exists an infinite B2[g] sequence A = {ak} such that ak ≤ k^2＋1/g（log k）^1/g＋0（1） as k→∞. The exponent 2＋1/g improves the previous one, 2 ＋ 2/g, obtained by Erdos and Renyi in 1960. We obtain a similar result for B2 [g] sequences of squares.     

On scalar metrics that maximize geodesic distances in the plane

A Riemannian metric a in the plane together with a point ${A\subset \mathbb {R}^2}$ induces a distance function d _a (A, ·). We investigate the optimization problem searching a scalar metric a which maximizes the distance between A and a given set B. We find necessary conditions for optimal metrics which help to determine solutions a. In the case that the set B is a single point, we determine the optimal metric explicitly.     

A result about determinantal divisors

Let Rbe a principal ideal ringR_n the ring of n× nmatrices over R, and d_k (A) the kth determinantal divisor of Afor 1 ? k? n, where Ais any element of R_n , It is shown that if A,BεR_n , det(A) det(B:) ≠ 0, then d_k (AB) ≡ 0 mod d_k (A) d_k (B). If in addition (det(A), det(B)) = 1, then it is also shown that d_k (AB) = d_k (A) d_k (B). This provides a new proof of the multiplicativity of the Smith normal form for matrices with relatively prime determinants.     

NON-EMPTY CROSS-2-INTERSECTING FAMILIES OF SUBSETS

Let Cdenote the set of all k-subests of an n-set.Assume Alohtain in Ca,and A lohtain in (A,B) is called a cross-2-intersecting family if |A B≥2 for and A∈A,B∈B.In this paper,the best upper bounds of the cardinalities for non-empty cross-2-intersecting familles of a-and b-subsets are obtained for some a and b,A new proof for a Frankl-Tokushige theorem[6] is also given.     

Block partitions of sequences

Given a sequence A = (a ₁, …, a _n ) of real numbers, a block B of A is either a set B = {a _i , a _i+1, …, a _j } where i ≤ j or the empty set. The size b of a block B is the sum of its elements. We show that when each a _i ∈ [0, 1] and k is a positive integer, there is a partition of A into k blocks B ₁, …, B _k with |b _i ?b _j | ≤ 1 for every i, j. We extend this result in several directions.     

The choice number of random bipartite graphs

A random bipartite graphG(n, n, p) is obtained by taking two disjoint subsets of verticesA andB of cardinalityn each, and by connecting each pair of verticesaA andbB by an edge randomly and independently with probabilityp=p(n). We show that the choice number ofG(n, n, p) is, almost surely, (1+o(1))log₂(np) for all values of the edge probabilityp=p(n), where theo(1) term tends to 0 asnp tends to infinity.Research supported in part by a USA-Israeli BSF grant, a grant from the Israel Science Foundation, a Sloan Foundation grant No. 96-6-2 and a State of New Jersey grant.Research supported by an IAS/DIMACS Postdoctoral Fellowship.     

一四元数矩阵方程组的广义(反)反射解

该文给出了四元数矩阵方程组X_1B_1=C_1,X_2B_2=C2,A_1X_1B_3+A_2X_2B_4=C_b可解的充要条件及其通解的表达式,利用此结果建立了四元数矩阵方程组XB_a=C_a,A_bXB_b=C_b有广义(反)反射解的充要条件及其有此种解时通解的表达式.     

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

Collinear subsets of lattice point sequences—An analog of Szemerédi's theorem

Szemerédi's theorem states that given any positive number B and natural number k, there is a number n(k, B) such that if n ? n(k, B) and 0 < a₁ < … < a_n is a sequence of integers with a_n ? Bn, then some k of the a_i form an arithmetic progression. We prove that given any B and k, there is a number m(k, B) such that if m ? m(k, B) and u₀, u₁, …, u_m is a sequence of plane lattice points with ∑_i=1^m…u_i ? u_i?1… ? Bm, then some k of the u_i are collinear. Our result, while similar to Szemerédi's theorem, does not appear to imply it, nor does Szemerédi's theorem appear to imply our result.     

Approximating reversal distance for strings with bounded number of duplicates

For a string A=a₁…a_n, a reversalρ(i,j), 1?i?j?n, transforms the string A into a string A^′=a₁…a_i-1a_ja_j-1…a_ia_j+1…a_n, that is, the reversal ρ(i,j) reverses the order of symbols in the substring a_i…a_j of A. In the case of signed strings, where each symbol is given a sign + or -, the reversal operation also flips the sign of each symbol in the reversed substring. Given two strings, A and B, signed or unsigned, sorting by reversals (SBR) is the problem of finding the minimum number of reversals that transform the string A into the string B.Traditionally, the problem was studied for permutations, that is, for strings in which every symbol appears exactly once. We consider a generalization of the problem, k-SBR, and allow each symbol to appear at most k times in each string, for some k?1. The main result of the paper is an O(k²)-approximation algorithm running in time O(n). For instances with , this is the best known approximation algorithm for k-SBR and, moreover, it is faster than the previous best approximation algorithm.     

Global convergence properties of two modified BFGS-type methods

This article studies a modified BFGS algorithm for solving smooth unconstrained strongly convex minimization problem. The modified BFGS method is based on the new quasi-Newton equation B_k+1s_k=yk where y_k*, =yk + A_ks_k andA _k is a matrix. Wei, Li and Qi [WLQ] have proven that the average performance of two of those algorithms is better than that of the classical one. In this paper, we prove the global convergence of these algorithms associated to a general line search rule.