On the improvement per iteration in Karmarkar's algorithm for linear programming

We investigate the decrease in potential at an iteration of Karmarkar's projective method for linear programming. For a fixed step length parameter (so that we must have 0 < 1) the best possible guarantee _n () inn dimensional space is essentially ln 2 0.69; and to achieve this we must take about 1. Indeed we show the precise result that _n () equals ln(1 +)-ln(1 –/(n – 1)) forn sufficiently large. If we choose an optimal step length at each iteration then this guarantee increases only to about ^* 0.72. We also shed some light on the remarkable empirical observation that the number of iterations required seems scarcely to grow with the size of the problem.     

Improved lower bounds on the length of Davenport-Schinzel sequences

We derive lower bounds on the maximal length _s(n) of (n, s) Davenport Schinzel sequences. These bounds have the form _2s=1(n)=(n^s(n)), where(n) is the extremely slowly growing functional inverse of the Ackermann function. These bounds extend the nonlinear lower bound ₃ (n)=(n(n)) due to Hart and Sharir [5], and are obtained by an inductive construction based upon the construction given in [5].Work on this paper has been supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation.     

A note onn-groupoids linearly defined on fields

On the real fieldR and the Galois fields GF(p), define operations by [x₁ x₂ ···x_n]=₁x₁+₂x₂+ ··· +_nx_n, where ₁,₂, ...,_n are elements of the relevant fields. LetB be the class of alln-groupoids defined on Galois fields in this way. In this paper, we will study the variety generated byB and the variety generated by the algebra (R, [ ]), where ₁,...,_n are algebraically independent inR. We will study also varieties defined in a similar way with the operation [x₁, x₂,..., x_n]=(x₁+x₂+ ···+x_n).Presented by Jan Mycielski.The author thanks Professor T. Evans for his suggestions in developing this article.     

On a generalized Eulerian distribution

The distribution with probability function p _k(n, , ) = A _{n, k}(, )/(+ )^[p], k = 0, 1, 2, ..., n, where the parameters and are positive real numbers, A _{n, k} (, ) is the generalized Eulerian number and ( + )^[n] = ( + )( + +1) ... ( + +n – 1), introduced and discussed by Janardan (1988, Ann. Inst. Statist. Math., 40, 439–450), is further studied. The probability generating function of the generalized Eulerian distribution is expressed by a generalized Eulerian polynomial which, when expanded suitably, provides the factorial moments in closed form in terms of non-central Stirling numbers. Further, it is shown that the generalized Eulerian distribution is unimodal and asymptotically normal.     

Convergence of automorphisms of compact projective planes

We show that a pointwise convergent sequence ( _n) _nN of continuous collineations of a compact projective plane converges uniformly if and only if the pointwise limit of ( _n) _nN has a quadrangle in its image. Moreover is then a continuous collineation. Furthermore, we derive that a homomorphism between topological projective planes is continuous if and only if it is continuous at some point.Supported by DFG/Graduiertenkolleg.     

On depth first search strees inm-out digraphs

We consider depth first search (DFS for short) trees in a class of random digraphs: am-out model. Let _i be thei ^th vertex encountered by DFS andL(i, m, n) be the height of _i in the corresponding DFS tree. We show that ifi/n asn, then there exists a constanta(,m), to be defined later, such thatL(i, m, n)/n converges in probability toa(,m) asn. We also obtain results concerning the number of vertices and the number of leaves in a DFS tree.     

Uniformization and the Poincaré metric on the leaves of a foliation by curves

In this paper we prove that a holomorphic foliation by curves, on a complex compact manifoldM, whose singularities are non degenerated and whose tangent line bundle admits a metric of negative curvature, satisfies the following properties:(a): All leaves are hyperbolic.(b): The Poincaré metric on the leaves is continuous.(c): The set of uniformizations of the leaves by the Poincaré disc D is normal. Moreover, if ( _n ) _n 1 is a sequence of uniformizations which converges to a map : D, then either is a constant map (a singularity), or is an uniformization of some leaf. This result generalizes Theorem B of [LN], in which we prove the same facts for foliations of degree 2 on projective spaces.This research was partially supported by Pronex-Dynamical Systems, FINEP-CNPq.     

On monotone and convex approximation by algebraic polynomials

The following results are obtained: If >0, 2, [3, 4], andf is a nondecreasing (convex) function on [–1, 1] such thatE _n (f) n ^– for any n>, then E _n ⁽¹⁾ (f)Cn ^– (E _n ⁽²⁾ (f)Cn ^–) for n>, where C=C(), E_n(f) is the best uniform approximation of a continuous function by polynomials of degree (n–1), and E _n ⁽¹⁾ (f) (E _n ⁽²⁾ (f)) are the best monotone and convex approximations, respectively. For =2 ( [3, 4]), this result is not true.Published in Ukrainskii Matematicheskii Zhurnal, Vol. 46, No. 9, pp. 1266–1270, September, 1994.     

A result from diophantine approximation which has applications in economics

We say that a real number allows poor approximations if we can find 0<=()<1 and a sequence of integers n₁2<... such that for all rationals p/q with qn. we have |–.p/q| > Kn _j ^–l– where K is a constant depending only on .In this note we prove that the set of numbers which allow poor approximations are precisely the very well-approximable numbers.The existence of numbers with poor approximations has been used by Cheng [1] to show the existence of a dense set of economies whose cone converges to the Walras equilibrium as slowly as 0(n^–1/2–) after n replications.     

Compact interval spaces in which all closed subsets are homeomorphic to clopen ones,I

A topological space X whose topology is the order topology of some linear ordering on X, is called an interval space. A space in which every closed subspace is homeomorphic to a clopen subspace, is called a CO space. We regard linear orderings as topological spaces, by equipping them with their order topology. If L and K are linear orderings, then L ^*, L+K, L·K denote respectively the reverse orderings of L, the ordered sum of L and K and the lexicographic order on L×K (so ·2=+ and 2·=). Ordinals are considered as linear orderings, and cardinals are initial ordinals. For cardinals , 0, let L(, )= + 1 + ^* . Main theorem. Let X be a compact interval space. Then X is a CO space if and only if X is homeomorphic to a space of the form + 1 + _i L( _i , _i ), where is any ordinal, n, for every ii, _i are regular cardinals and _{i i}, and if n>0, then max({ _i: i}) · . This first part is devoted to show the following result. Theorem: If X is a compact interval CO space, then X is a scattered space (that means that every subspace of X has an isolated point).Supported by the Université Claude-Bernard (Lyon-1), the Ben Gurion University of the Negev, and the C.N.R.S.: UPR 9016Supported by the City of Lyon     

On Sums of Projections

In the paper, for all n, we describe the set _n of all real numbers admitting a collection of projections P ₁,...,P _n on a Hilbert space H such that _k=1 ⁿ P _k= I (I is the identity operator on H) and study the problem to find all collections of this kind for a given _n .     

A Bernstein result for energy minimizing hypersurfaces

We show that there are no entire, positive, stable solutions in ⁿ of the Euler equation corresponding to the singular variational integral ,>0, if+n<5.236.... Furthermore we prove a related result for smooth boundaries of least-energy |x _n+1||D _U | in ⁿ⁺¹.     

Fractional integrodifferentiation in Hölder classes of arbitrary order

Hölder classes of variable order (x) are introduced and it is shown that the fractional integralI ₀₊ has Hölder order (x)+ (0 < , ₊, +₊ < 1, ₊ = sup (x)).     

Finding the αn-th largest element

We describe an algorithm for selecting the n-th largest element (where 0<<1), from a totally ordered set ofn elements, using at most (1+(1+o(1))H())·n comparisons whereH() is the binary entropy function and theo(1) stands for a function that tends to 0 as tends to 0. For small values of this is almost the best possible as there is a lower bound of about (1+H())·n comparisons. The algorithm obtained beats the global 3n upper bound of Schönhage, Paterson and Pippenger for <1/3.     

On the Measure of a Nonreciprocal Algebraic Number

Let M() be the Mahler measure of an algebraic number and let G() be the modulus of the product of logarithms of absolute values of its conjugates. We prove that if is a nonreciprocal algebraic number of degree d 2 then M()² G()^1/d 1/2d. This estimate is sharp up to a constant. As a main tool for the proof we develop an idea of Cassels on an estimate for the resultant of and 1/. We give a number of immediate corollaries, e.g., some versions of Smyth's inequality for the Mahler measure of a nonreciprocal algebraic integer from below.     

Extensions of Laguerre operators in indefinite inner product spaces

The Laguerre-Sonin polynomialsL _n ⁽⁾ are orthogonal in linear spaces with indefinite inner product if<–1. We construct the completion () of this space and describe self-adjoint extensions of the Laguerre operatorl(y)=xy+(1+–x)y,<–1, in the space (). In particular, we write out the self-adjoint extension of the Laguerre operator whose eigenfunctions coincide with the Laguerre-Sonin polynomials and form an orthogonal basis in ().Translated fromMatematicheskie Zametki, Vol. 63, No. 4, pp. 509–521, April, 1998.This research was partially supported by the INTAS foundation under grant No. 93-02449.     

On some classes of modules

The aim of this paper is to investigate quasi-corational, comonoform, copolyform and -(co)atomic modules. It is proved that for an ordinal a right R-module M is -atomic if and only if it is -coatomic. And it is also shown that an -atomic module M is quasi-projective if and only if M is quasi-corationally complete. Some other results are developed.     

Empirical and Poisson processes on classes of sets or functions too large for central limit theorems

Summary Let P be the uniform probability law on the unit cube I ^d in d dimensions, and P _n the corresponding empirical measure. For various classes of sets AI ^d , upper and lower bounds are found for the probable size of sup {¦P _n –P) (A)¦ A }. If is the collection of lower layers in I ², or of convex sets in I ³, an asymptotic lower bound is ((log n)/n) ^1/2(log log n)^––1/2 for any >0. Thus the law of the iterated logarithm fails for these classes.If >0, is the greatest integer <, and 0 d f(x₁,...,x _d-1)} where f has all its partial derivatives of orders bounded by K and those of order satisfy a uniform Hölder condition ¦D ^p (f(x)–f(y))¦K¦x –y¦ ^–. For 0<–/(d–1+) for a constant = (d,)>0. When = d-1 the same lower bound is obtained as for the lower layers in I ² or convex sets in I ³. For 0 – 1 there is also an upper bound equal to a power of log n times the lower bound, so the powers of n are sharp.This research was partially supported by National Science Foundation Grant MCS-79-04474     

The self-similar solutions to a fast diffusion equation

A quasilinear equation u -x·u/2+f(u)=0 is studied, wheref(u)=–u+u , > 0, 0<. <1, >1 andx R ⁿ. The equation arises from the study of blow-up self-similar solutions of the heat equation _t =+. We prove the existence and non-existence of ground state for various combination of , and . In particular, we prove that when / < forn=1,2 or / < (n + 2) /(n – 2) forn 3 there exists no non-constant positive radial self-similar solution of the parabolic equation, but for many cases where / > (n + 2)/(n – 2) there exists an infinite number of non-constant positive radial self-similar solutions.