A decomposition of 2-weak vertex-packing polytopes

The 2-weak vertex-packing polytope of a loopless graphG withd vertices is the subset of the unitd-cube satisfyingx _i +x _j ≤1 for every edge (i,j) ofG. The dilation by 2 of this polytope is a polytope with integral vertices. We triangulate with lattice simplices of minimal volume and label the maximal simplices with elements of the hyperoctahedral groupB _d . This labeling gives rise to a shelling of the triangulation of , where theh-vector of (and the Ehrharth ^*-vector of can be computed as a descent statistic on a subset ofB _d defined in terms ofG. A recursive way of computing theh-vector of is also given, and a recursive formula for the volume of . This work was partially supported by grants from the Icelandic Council of Science and the Royal Swedish Academy of Sciences, respectively.     

Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice

Let _i(L), _i(L^*) denote the successive minima of a latticeL and its reciprocal latticeL ^*, and let [b₁,..., b _n ] be a basis ofL that is reduced in the sense of Korkin and Zolotarev. We prove that and, where and _j denotes Hermite's constant. As a consequence the inequalities are obtained forn7. Given a basisB of a latticeL in ^m of rankn andx ^m , we define polynomial time computable quantities(B) and(x,B) that are lower bounds for ₁(L) and(x,L), where(x,L) is the Euclidean distance fromx to the closest vector inL. If in additionB is reciprocal to a Korkin-Zolotarev basis ofL ^*, then ₁(L) _n ^* (B) and.The research of the second author was supported by NSF contract DMS 87-06176. The research of the third author was performed at the University of California, Berkeley, with support from NSF grant 21823, and at AT&T Bell Laboratories.     

Large sample theory for distributions on the hypersphere with rotational symmetries

Summary A distribution on the unit sphere inℝ ^q with a densityf(‖x _v ‖) is considered where is ans(<q) dimensional subspace andx _v is the part ofx in . For a large sample the estimation of , a test that and a test for rotational symmetry within is given. For several samples with possibly different subspaces but the samef, a test that is given. For all tests power functions for contiguous alternatives are given. For the special density proportional to expk‖x _v ‖ ², additional results are given. Research supported in part by a Contract with the Office of Naval Research N00014-81-K-0146 awarded to Princeton University, Princeton, New Jersey 08544.     

A generalized inverse ∈-algorithm for constructing intersection projection matrices,with applications

Givenk linear manifolds ₁, ..., _k and corresponding perpendicular projection matricesP ₁, ...,P _k , a closed formula is derived for the perpendicular projection matrix with range. The derivation uses results taken from the theory of generalized inverses together with an application ofWynn's -Algorithm to a convergent sequence of matrices. A variant of this formula is then used in solving arbitrary complex linear systems by iteration and in computing generalized inverses; the latter application provides a solution to least squares linear regression problems.A preliminary version of this paper, MRC Technical Summary Report 604, was sponsored by the Mathematics Research Center, United States Army, Madison, Wisconsin, under Contract No.: DA-11-022-ORD-20$9.     

Hankel-Schur multipliers and multipliers of the space H1

In this paper there is given a sufficient condition for a Hankel matrix _F to belong to the space of Schur multipliers of all bounded operators in ² (or, what is the same, to the tensor algebra V²). It is shown that ifw is a nonnegative function on T, such that is a sequence of integers, {F_i}_j1 is a sequence of polynomials,) and, then _FV². It follows from this that under these conditions F is a multiplier of the space H¹, i.e.,.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 135, pp. 113–119, 1984     

Stochastic dilations of uniformly continuous completely positive semigroups

For an arbitrary uniformly continuous completely positive semigroup ( _t :t0) on the space of bounded operators on a Hilbert space, we construct a family (U(t)t0) of unitary operators on a Hilbert space and a conditional expectation from to, such that, for arbitraryt0,. The unitary operatorsU(t) satisfy a stochastic differential equation involving a noncommutative generalisation of infinite dimensional Brownian motion. They do not form a semigroup.Part of this work was completed when the first author was visiting research associate at the Center for Relativity, Physics Department, The University of Texas at Austin, Austin, TX 78712, U.S.A., supported in part by NSF PHY 81-01381.     

Inductive definitions,models of comprehension and invariant definability

The connections between inductive definability and models of comprehension are studied. Let = 〈A, R _l, ...,R _n 〉 be an infinite structure and letI _φ be a set inductively defined by a formulaφ of the second order language . We prove that if is a model of Δ ₁ ¹ -Comprehension relativized toφ, andφ is -absolute, then for everyη smaller than the height of (h( )),I _φ is in . If is aβ-structure which satisfies Σ ₁ ¹ -Comprehension relativized toφ and WF(X), and φ is -absolute, thenI _φ is in and ‖φ| <h ( ). These results imply that Barwise-Grilliot theorem is false in the case of uncountable acceptable structures. We also study the notion of invariant definability over models₁ of Δ ₁ ¹ -Comprehension. This paper is registered as Report ZW 69/76 of the Mathematical Centre.     

An Inequality Involving the Local Eigenvalues of a Distance-Regular Graph

Let denote a distance-regular graph with diameter D 3, valency k, and intersection numbers a _i, b _i, c _i. Let X denote the vertex set of and fix x X. Let denote the vertex-subgraph of induced on the set of vertices in X adjacent X. Observe has k vertices and is regular with valency a ₁. Let _{1 2} ··· _k denote the eigenvalues of and observe ₁ = a ₁. Let denote the set of distinct scalars among ₂, ₃, ..., _k . For let mult denote the number of times appears among ₂, ₃,..., _k . Let denote an indeterminate, and let p ₀, p₁, ...,p _D denote the polynomials in [] satisfying p ₀ = 1 andp _i = c _i+1 p _i+1 + (a _i – c _i+1 + c _i)p _i + b _i p _i–1 (0 i D – 1),where p _–1 = 0. We show where we abbreviate = –1 – b ₁(1+)^–1. Concerning the case of equality we obtain the following result. Let T = T(x) denote the subalgebra of Mat _X ( ) generated by A, E*₀, E*₁, ..., E* _D , where A denotes the adjacency matrix of and E* _i denotes the projection onto the ith subconstituent of with respect to X. T is called the subconstituent algebra or the Terwilliger algebra. An irreducible T-module W is said to be thin whenever dimE* _i W 1 for 0 i D. By the endpoint of W we mean min{i|E* _i W 0}. We show the following are equivalent: (i) Equality holds in the above inequality for 1 i D – 1; (ii) Equality holds in the above inequality for i = D – 1; (iii) Every irreducible T-module with endpoint 1 is thin.     

Gauge group and gauge transformation in the continual theory of defects

A representation of the algebra (3)=t(3) S0(3, ) by differential Schaefer's operators is proposed, and an external algebra of (3)-valued differential forms is constructed. The requirement of local gauge invariance is formulated in the model of the (3)-valued field, which enables a group of gauge transformations of the continual theory of defects to be obtained.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 190, pp. 173–184, 1991.I wish to thank V. N. Popov for his interest.     

Convex minimization under Lipschitz constraints

We consider the problem of minimizing a convex functionf(x) under Lipschitz constraintsf _i (x)0,i=1,...,m. By transforming a system of Lipschitz constraintsf _i (x)0,i=l,...,m, into a single constraints of the formh(x)-x²0, withh(·) being a closed convex function, we convert the problem into a convex program with an additional reverse convex constraint. Under a regularity assumption, we apply Tuy's method for convex programs with an additional reverse convex constraint to solve the converted problem. By this way, we construct an algorithm which reduces the problem to a sequence of subproblems of minimizing a concave, quadratic, separable function over a polytope. Finally, we show how the algorithm can be used for the decomposition of Lipschitz optimization problems involving relatively few nonconvex variables.     

An algorithm for constructing an optimal structural schedule

The article is devoted to the problem of finding an optimal schedule for a class of functionals ƒ which allows for the existence of a structural set of activities. The functionalƒ(R), where, is defined in the following way: where {_i(t)} is a structural set of functions, and the function F is defined on any finite set of arguments and satisfies the following conditions: 1)F(x)=(x); 2) F(x₁,x₂)=(x₁,x₂), F(x₁,x₂,...x₃)= (x₁, F(x₂,...,x_s)), S2; 3) and do not decrease in each of their arguments, and moreover, 3a) strictly increases with the increase of both arguments, 3b) if (x₁,x₂)>(x₁, x₂ (x₂, x₃)> (x₂,x₃), then F(x₁,x₂,x₃)>F(x₁,x₂,x₃).Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 124, pp. 5–20, 1983.     

Isoperimetric inequalities for infinite hyperplane systems

Let be an infinite discrete system ofk-dimensional flats inn-dimensional Euclidean space. If the totalk-dimensional volume of the flats in intersected with the ball of center 0 and radiusr, divided by the volume of that ball, tends to a limit forr→∞, then this limit is called thedensity of . We consider isoperimetric problems of the following kind. If is a hyperplane system of positive density, find sharp upper bounds for the density of the system ofk-flats (k∈{0, ...,n−2}) that are generated as intersections of hyperplanes in . Ideas from the theory of uniform distribution of sequences are employed to define a large class of hyperplane systems, calleduniform, for which all necessary densities exist, isperimetric inequalities can be proved, and systems with extremal intersection densities can be characterized.     

On the oscillatory and asymptotic behavior of the bounded solutions of differential equations with deviating arguments

Summary This paper is dealing with the oscillatory and asymptotic behavior of the bounded solutions of n-th order (n>1) differential equations with deviating arguments involving the so called r-derivatives D _r ^(i)x (i=0, 1, ..., n) of the unknown function x defined by , where r_i (i=1, 2, ..., n−1) are positive continuous functions on the interval [t ₀ , ∞). The fundamental purpose is to find a necessary and sufficient condition in order to have at least one (bounded nonoscillatory) solution whose the limit at ∞ exists inR−{0}. Entrata in Redazione il 29 giugno 1977. This paper is a part of the author's Doctoral Thesis submitted to the School of Physics and Mathematics of the University of Ioannina.     

Symmetric centres of braided monoidal categories

This paper introduces the concept of ‘symmetric centres’ of braided monoidal categories. LetH be a Hopf algebra with bijective antipode over a fieldk. We address the symmetric centre of the Yetter-Drinfel’d module category: and show that a left Yetter-Drinfel’d moduleM belongs to the symmetric centre of and only ifM is trivial. We also study the symmetric centres of categories of representations of quasitriangular Hopf algebras and give a sufficient and necessary condition for the braid of, _Hℳ to induce the braid of , or equivalently, the braid of , whereA is a quantum commutativeH-module algebra     

Approximation of the Distribution of the Supremum of a Centered Random Walk. Application to the Local Score

Let (X _n ) _{n 0} be a real random walk starting at 0, with centered increments bounded by a constant K. The main result of this study is: |P(S _n n x)–P( sup_{0 u 1} B _u x)| C(n,K) n/n, where x 0, ² is the variance of the increments, S _n is the supremum at time n of the random walk, (B _u ,u 0) is a standard linear Brownian motion and C(n,K) is an explicit constant. We also prove that in the previous inequality S _n can be replaced by the local score and sup₀ u 1 B _u by sup₀ u 1|B _u |.     

On the entropic regularization method for solving min-max problems with applications

Consider a min-max problem in the form of min _xX max_1im {f _i (x)}. It is well-known that the non-differentiability of the max functionF(x) max_1im {f _i (x)} presents difficulty in finding an optimal solution. An entropic regularization procedure provides a smooth approximationF _p(x) that uniformly converges toF(x) overX with a difference bounded by ln(m)/p, forp > 0. In this way, withp being sufficiently large, minimizing the smooth functionF _p(x) overX provides a very accurate solution to the min-max problem. The same procedure can be applied to solve systems of inequalities, linear programming problems, and constrained min-max problems.This research work was supported in part by the 1995 NCSC-Cray Research Grant and the National Textile Center Research Grant S95-2.     

Formal language theory and the geometry of 3-manifolds

Automatic groups were introduced in connection with geometric problems, in particular with the study of fundamental groups of 3-manifolds. In this article the class of automatic groups is extended to include the fundamental group of every compact 3-manifold which satisfies Thurston's geometrization conjecture. Toward this end, the class of asynchronously groups is introduced and studied, where is an arbitrary full abstract family of languages. For example may be the family of regular languagesReg, context-free languagesCF, or indexed languagesInd. The class consists of precisely those groups which are asynchronously automatic. It is proved that contains all of the above fundamental groups, but that does not. Indeed a virtually nilpotent group belongs to if and only if it is virtually abelian. The first author was partially supported by NSF grant DMS-9203500 and FNRS (Suisse). He also wishes to thank the University of Geneva for its hospitality while this paper was being written. The second author thanks the Institute for Advanced Study for its hospitality while this paper was being written.     

Taut Distance-Regular Graphs of Odd Diameter

Let denote a bipartite distance-regular graph with diameter D 4, valency k 3, and distinct eigenvalues ₀ > ₁ > ··· > _D. Let M denote the Bose-Mesner algebra of . For 0 i D, let E _i denote the primitive idempotent of M associated with _i . We refer to E ₀ and E _D as the trivial idempotents of M. Let E, F denote primitive idempotents of M. We say the pair E, F is taut whenever (i) E, F are nontrivial, and (ii) the entry-wise product E F is a linear combination of two distinct primitive idempotents of M. We show the pair E, F is taut if and only if there exist real scalars , such that _{i + 1 i + 1} – _{i – 1 i – 1} = _i ( _{i + 1} – _{i – 1}) + _i ( _{i + 1} – _{i – 1}) + (1 i D – 1)where ₀, ₁, ..., _D and ₀, ₁, ..., _D denote the cosine sequences of E, F, respectively. We define to be taut whenever has at least one taut pair of primitive idempotents but is not 2-homogeneous in the sense of Nomura and Curtin. Assume is taut and D is odd, and assume the pair E, F is taut. We show

Some finiteness conditions on indecomposable operands

Let S be a monoid such that every left S-operand satisfies the ascending chain condition on orbits. Let X be an indecomposable [0-indecomposable] left S-operand. There is a descending chain of suboperands of X defined in terms of maximal orbits. If this chain terminates after a finite number of terms, the last non-empty [non-zero] term defines a distinguished collection (X) [ ₀(X)] of disjoint [0-disjoint] orbits in X. The assumption that (X) [ ₀(X)] is finite for all appropriate X, together with the additional assumption that every left S-operand satisfies the d.c.c. on orbits, implies that S has a unique minimal left ideal [that the principal left ideals outside of the minimal ideal are linearly ordered]. This research supported in part by the National Science Foundation.     

Structures of polyhedra determined by submodular functions on crossing families

The present paper shows that for any submodular functionf on a crossing family with , if the polyhedron is nonempty, then there exist a unique distributive lattice with and a unique submodular function with such thatB(f) coincides with the base polyhedron associated with the submodular system . Here, iff is integer-valued, thenf ₁ is also integer-valued. Based on this fact, we also show the relationship between the independent-flow problem considered by the author and the minimum cost flow problem considered by J. Edmonds and R. Giles.