The inverse M-matrix problem

One aspect of the inverse M-matrix problem can be posed as follows. Given a positive n × n matrix A=(a_ij) which has been scaled to have unit diagonal elements and off-diagonal elements which satisfy 0 < y ? a_ij ? x < 1, what additional element conditions will guarantee that the inverse of A exists and is an M-matrix? That is, if A^?1=B=(b_ij), then b_ii> 0 and b_ij ? 0 for i≠_j. If n=2 or x=y no further conditions are needed, but if n ? 3 and y < x, then the following is a tight sufficient condition. Define an interpolation parameter s via x²=sy+(1?s)y²; then B is an M-matrix if s^?1 ? n?2. Moreover, if all off-diagonal elements of A have the value y except for a_ij=a_jj=x when i=n?1, n and 1 ? _j ? n?2, then the condition on both necessary and sufficient for B to be an M-matrix.     

Quasiplanar Diagrams and Slim Semimodular Lattices

For elements x and y in the (Hasse) diagram D of a finite bounded poset P, x is on the left of y, written as x λ y, if x and y are incomparable and x is on the left of all maximal chains through y. Being on the right, written as x ? y, is defined analogously. The diagram D is quasiplanar if λ and ? are transitive and for any pair (x,y) of incomparable elements, if x is on the left of some maximal chain through y, then x λ y. A planar diagram is quasiplanar, and P has a quasiplanar diagram iff its order dimension is at most 2. We are interested in diagrams only up to similarity. A finite lattice is slim if it is join-generated by the union of two chains. The main result gives a bijection between the set of (the similarity classes of) finite quasiplanar diagrams and that of (the similarity classes of) planar diagrams of finite slim semimodular lattices. This bijection allows one to describe finite posets of order dimension at most 2 by finite slim semimodular lattices, and conversely. As a corollary, we obtain that there are exactly (n?2)! quasiplanar diagrams of size n.     

Idempotent Totally Symmetric Operations on Finite Posets

An n-ary operation f is totally symmetric if it obeys the identity f(x ₁,...,x _n )=f(y ₁,...,y _n ) for all sets of variables such that {x ₁,...,x _n }={y ₁,...,y _n }. We characterize finite posets admitting an n-ary idempotent totally symmetric operation for all n. The characterization is expressed in terms of zigzags, special objects related to the poset. Some open problems concerning idempotent Malcev conditions for order primal algebras are mentioned.     

On the Rédei zeta function

Let L be a locally finite lattice. An order function ν on L is a function defined on pairs of elements x, y (with x ≤ y) in L such that ν(x, y) = ν(x, z) ν(z, y). The Rédei zeta function of L is given by ?(s; L) = Σ_x∈Lμ(Ô, x) ν(Ô, x)^?s. It generalizes the following functions: the chromatic polynomial of a graph, the characteristic polynomial of a lattice, the inverse of the Dedekind zeta function of a number field, the inverse of the Weil zeta function for a variety over a finite field, Philip Hall's φ-function for a group and Rédei's zeta function for an abelian group. Moreover, the paradigmatic problem in all these areas can be stated in terms of the location of the zeroes of the Rédei zeta function.     

On almost-quasi-commutative rings

A ring R is called almost-quasi-commutative if for each x, y ∈ R there exist nonzero relatively prime integers j = j(x, y) and k = k(x, y) and a non-negative integer n = n(x, y) such that jxy = k(yx) ⁿ . We establish some general properties of such rings, study commutativity of almost-quasi-commutative R, and consider several examples.     

Intersections of Schubert varieties and eigenvalue inequalities in an arbitrary finite factor

The intersection ring of a complex Grassmann manifold is generated by Schubert varieties, and its structure is governed by the Littlewood-Richardson rule. Given three Schubert varieties S₁, S₂, S₃ with intersection number equal to one, we show how to construct an explicit element in their intersection. This element is obtained generically as the result of a sequence of lattice operations on the spaces of the corresponding flags, and is therefore well defined over an arbitrary field of scalars. Moreover, this result also applies to appropriately defined analogues of Schubert varieties in the Grassmann manifolds associated with a finite von Neumann algebra. The arguments require the combinatorial structure of honeycombs, particularly the structure of the rigid extremal honeycombs. It is known that the eigenvalue distributions of self-adjoint elements a,b,c with a+b+c=0 in the factor Rω are characterized by a system of inequalities analogous to the classical Horn inequalities of linear algebra. We prove that these inequalities are in fact true for elements of an arbitrary finite factor. In particular, if x,y,z are self-adjoint elements of such a factor and x+y+z=0, then there exist self-adjoint a,b,c∈Rω such that a+b+c=0 and a (respectively, b,c) has the same eigenvalue distribution as x (respectively, y,z). A (‘complete’) matricial form of this result is known to imply an affirmative answer to an embedding question formulated by Connes. The critical point in the proof of this result is the production of elements in the intersection of three Schubert varieties. When the factor under consideration is the algebra of n×n complex matrices, our arguments provide new and elementary proofs of the Horn inequalities, which do not require knowledge of the structure of the cohomology of the Grassmann manifolds.     

Clones satisfying the term condition

The term condition considered here is the property of an operation ? that holds iff ? and all of its variants obtained by permuting the variables satisfy (for all x,y,u₁,…v₁,…)$\text{?(x,u}{}_1\text{,…) = ?(x,v}{}_1\text{…)??(y,u}{}_1\text{,…) = ?(y,v)}{}_1\text{,…)}$. Clones consisting entirely of operations satisfying this term condition are called TC clones; algebras whose clone of term operations is a TC clone are called TC algebras; varieties such that every algebra in the variety is a TC algebra are called TC varieties. The paper is a systematic study of these notions, giving primary attention to operations and algebras on finite base sets, and to varieties generated by finite algebras. It is proved, among other results, that the number of n-ary TC operations on a k-element set is logarithmically asymptotic to k^(k?1)n when n increases without bound and k is held fixed; that there exist only countably many TC clones on any finite set; that the maximal TC clones on a finite set are finite in number (for each set). Some necessary conditions for an algebra to generate a TC variety are given, also some sufficient conditions.     

Stop rule and supremum expectations of i.i.d. random variables: A complete comparison by conjugate duality

A complete comparison is made between the value V(X₁,…, X_n) = sup{EX_t: t is a stop rule for X₁,…,X_n} and E(max_{j ≤ n}X_j) for all uniformly bounded sequences of i.i.d. random variables X₁, …, X_n. Specifically, the set of ordered pairs {(x,y): x = V(X₁, …, X_n) and y = E(max_j≤nX_j) for some i.i.d.r.v.'s X₁,…, X_n taking values in [0, 1]} is precisely the set {(x, y): x≤y≤Γ_n(x); 0 ≤x≤1}, where the upper boundary function Γ_n is given in terms of recursively defined functions. The result yields families of inequalities for the “prophet” problem, relating the motal's value of a game V(X₁, …, X_n) to the prophet's value of the game E(max_j≤nX_j). The proofs utilize conjugate duality theory, probabilistic convexity arguments, and functional equation analysis. Asymptotic analysis of the “prophet” regions and inequalities is also given.     

A new inequality for symmetric functions

Let x_i ≥ 0, y_i ≥ 0 for i = 1,…, n; and let a_j(x) be the elementary symmetric function of n variables given by a_j(x) = ∑_{1 ≤ ii < … <ij ≤ n}x_ii … x_ij. Define the partical ordering x <y if a_j(x) ≤ a_j(y), j = 1,… n. We show that $\text{x}\text{\$}\text{?}\text{y ? x}{}^{\mathrm{\alpha }}\text{\$}\text{?}\text{y}{}^{\mathrm{\alpha }}\text{, 0}\text{\$}\text{?}\text{α ≤ 1}$, where {x^α}_i = x^α_i. We also give a necessary and sufficient condition on a function f(t) such that x <y ? f(x) <f(y). Both results depend crucially on the following: If x <y there exists a piecewise differentiable path z(t), with z_i(t) ≥ 0, such that z(0) = x, z(1) = y, and z(s) <z(t) if 0 ≤ s ≤ t ≤ 1.     

Finite embedding theorems for partial Latin squares,quasi-groups,and loops

In this paper we prove that a finite partial commutative (idempotent commutative) Latin square can be embedded in a finite commutative (idempotent commutative) Latin square. These results are then used to show that the loop varieties defined by any non-empty subset of the identities {x(xy) = y, (yx)x = y} and the quasi-group varieties defined by any non-empty subset of {x² = x, x(xy) = y, (yx)x = y}, except possibly {x(xy) = y, (yx)x = y}, have the strong finite embeddability property. It is then shown that the finitely presented algebras in these varities are residually finite, Hopfian, and have a solvable word problem.     

Lipschitz homeomorphisms of the Hilbert cube

We study the question whether the Hilbert cube Q is Lipschitz homogeneous. The answer depends on the metric of Q. For example, setting d(x,y)=sup_j|x_j-y_j|/j we obtain a Lipschitz homogeneous metric, but if the last j is replaced by j!, the answer is negative.     

Varieties of Birkhoff Systems Part II

This is the second part of a two-part paper on Birkhoff systems. A Birkhoff system is an algebra that has two binary operations ? and + , with each being commutative, associative, and idempotent, and together satisfying x?(x + y) = x+(x?y). The first part of this paper described the lattice of subvarieties of Birkhoff systems. This second part continues the investigation of subvarieties of Birkhoff systems. The 4-element subdirectly irreducible Birkhoff systems are described, and the varieties they generate are placed in the lattice of subvarieties. The poset of varieties generated by finite splitting bichains is described. Finally, a structure theorem is given for one of the five covers of the variety of distributive Birkhoff systems, the only cover that previously had no structure theorem. This structure theorem is used to complete results from the first part of this paper describing the lower part of the lattice of subvarieties of Birkhoff systems.     

A new approach to the dynamic maintenance of maximal points in a plane

A pointp _i=(x _i, y_i) in thex–y plane ismaximal if there is no pointp _j=(x _j, y_j) such thatx _j>x_i andy _j>y_i. We present a simple data structure, a dynamic contour search tree, which contains all the points in the plane and maintains an embedded linked list of maximal points so thatm maximal points are accessible inO(m) time. Our data structure dynamically maintains the set of points so that insertions takeO(logn) time, a speedup ofO(logn) over previous results, and deletions takeO((logn)²) time.The research of the first author was partially supported by the National Science Foundation under Grant No. DCR-8320214 and by the Office of Naval Research on Contract No. N 00014-86-K-0689. The research of the second author was partially supported by the Office of Naval Research on Contract No. N 00014-86-K-0689.     

Sharp probability estimates for random walks with barriers

We give sharp, uniform estimates for the probability that a random walk of n steps on the reals avoids a half-line [y,∞) given that it ends at the point x. The estimates hold for general continuous or lattice distributions provided the fourth moment is finite.     

Criteria for Invertibility of Elements in Associates

We continue the investigation of invertible elements in associates, i.e., in (n + 1)-ary groupoids that are (i, j)-associative for all i j (mod s), where s is a divisor of a number n. For s = 1, an arbitrary associate is a semigroup. We establish two new criteria for the invertibility of elements, which generalize the results obtained earlier, and formulate corollaries for (n + 1)-groups and polyagroups, i.e., quasigroup associates.     

A construction of orthogonal arrays and applications to embedding theorems

An n^t by k orthogonal array is a collection of k-tuples of elements from an n-set, such that if a matrix is formed with the k-tuples as rows then each ordered t-tuple of elements appears exactly once as a row of each t columned and n^t rowed submatrix. If such an array has its set of k-tuples invariant under the elements of a subgroup G of S_t then the array is referred to as a G-array. A method is described for constructing a G-array of order nr from an array of order n and G-arrays of order r.The above described construction is used to produce finite embedding theorems for partial 3-quasigroups of various types. For a class of 3-quasigroups, such a theorem shows that a finite partial member of the class can be embedded in a finite complete member of the class. Theorems included produce finite embedding theorems for 3-quasigroups satisfying the identities 〈x,y,〈y,x,z〉〉=z and 〈〈z,x,y〉,y,x〉=z, for cyclic 3-quasigroup s, and conditional embedding theorems are presented for semi-symmetric 3-quasigroups.     

Frankl's Conjecture Is True for Lower Semimodular Lattices

It is shown that every finite lower semimodular lattice L with |L|≥2 contains a join-irreducible element x such that at most |L|/2 elements y∈L satisfy y≥x. Revised: August 16, 1999     

Constructions for Permutation Codes in Powerline Communications

A permutation array (or code) of length n and distance d is a set Γ of permutations from some fixed set of n symbols such that the Hamming distance between each distinct x, y ∈ Γ is at least d. One motivation for coding with permutations is powerline communication. After summarizing known results, it is shown here that certain families of polynomials over finite fields give rise to permutation arrays. Additionally, several new computational constructions are given, often making use of automorphism groups. Finally, a recursive construction for permutation arrays is presented, using and motivating the more general notion of codes with constant weight composition.