Generalizations and applications of the nowhere zero linear mappings in network coding

In [2], Alon and Tarsi proposed a conjecture about the nowhere-zero point in linear mappings. In this paper, we first study some generalizations of this problem, and obtain necessary and sufficient conditions for the existence of nowhere point in these generalized problems under the assumption |F|?n+2, where n is the number of rows of the matrix A. Then we apply the results in these generalizations to give a polynomial time algebraic construction of the acyclic network codings.     

Reducibility number

Let P be a poset in a class of posets P. A smallest positive integer r is called reducibility number of P with respect to P if there exists a non-empty subset S of P with |S|=r and P-S∈P. The reducibility numbers for the power set 2ⁿ of an n-set (n?2) with respect to the classes of distributive lattices, modular lattices and Boolean lattices are calculated. Also, it is shown that the reducibility number r of the lattice of all subgroups of a finite group G with respect to the class of all distributive lattices is 1 if and only if the order of G has at most two distinct prime divisors; further if r is a prime number then order of G is divisible by exactly three distinct primes. The class of pseudo-complemented u-posets is shown to be reducible. Deletable elements in semidistributive posets are characterized.     

On nonconvexity of the solution set of a system of linear interval equations

We give necessary and sufficient conditions for the solution set of a system of linear interval equations to be nonconvex and derive some consequences.     

Projective mappings between projective lattice geometries

The concept of projective lattice geometry generalizes the classical synthetic concept of projective geometry, including projective geometry of modules.In this article we introduce and investigate certain structure preserving mappings between projective lattice geometries. Examples of these so-calledprojective mappings are given by isomorphisms and projections; furthermore all linear mappings between modules induce projective mappings between the corresponding projective geometries.     

Iterations of linear maps over finite fields

We study the dynamics of the evolution of Ducci sequences and the Martin-Odlyzko-Wolfram cellular automaton by iterating their respective linear maps on . After a review of an algebraic characterization of cycle lengths, we deduce the relationship between the maximal cycle lengths of these two maps from a simple connection between them. For n odd, we establish a conjugacy relationship that provides a more direct identification of their dynamics. We give an alternate, geometric proof of the maximal cycle length relationship, based on this conjugacy and a symmetry property. We show that the cyclic dynamics of both maps in dimension 2n can be deduced from their periodic behavior in dimension n. This link is generalized to a larger class of maps. With restrictions shared by both maps, we obtain a formula for the number of vectors in dimension 2n belonging to a cycle of length q that expresses this number in terms of the analogous values in dimension n.     

On geometric semilattices

We define geometric semilattices, a generalization of geometric lattices. The poset of independent sets of a matroid is another example. We prove several axiomatic and constructive characterizations, for example: geometric semilattices are those semilattices obtained by removing a principal filter from a geometric lattice. We also show that all geometric semilattices are shellable, unifying and extending several previous results.Partially supported by NSF grant MCS 81-03474.     

Lattices and infinite-dimensional forms. ‘The Lattice Method’

Hermitean vector spaces E of infinite dimensions are considered. Let G be a subgroup of the orthogonal group of E acting on a set M. The Lattice Method is a technique for classifying the orbits in M under G. We discuss the method in abstract terms and we illustrate it by means of three classification results showing that it is decisive to do a considerable amount of explicit calculations with vector subspace lattices.     

On cone orderings and the linear complementarity problem

This paper first generalizes a characterization of polyhedral sets having least elements, which is obtained by Cottle and Veinott [6], to the situation in which Euclidean space is partially ordered by some general cone ordering (rather than the usual ordering). We then use this generalization to establish the following characterization of the class $\text{C}$ of matrices ($\text{C}$ arises as a generalization of the class of Z-matrices; see [4], [13], [14]): M∈$\text{C}$ if and only if for every vector q for which the linear complementarity problem (q,M) is feasible, the problem (q,M) has a solution which is the least element of the feasible set of (q,M) with respect to a cone ordering induced by some simplicial cone. This latter result generalizes the characterizations of K-and Z-matrices obtained by Cottle and Veinott [6] and Tamir [21], respectively.     

Fixed points of posets and clique graphs

The fixed point property for partial orders has been the object of much attention in the past twenty years. Recently, M. Roddy ([7]) proved this famous conjecture of Rival (see [6]): the class of finite orders with the fixed point property is closed under finite products.In this article, we prove that a finite order has the fixed point property if the sequence of iterated clique graphs of its comparability graph tends to the trivial graph.     

Solving linear systems via Pfaffians

An explicit solution is given for the system of linear equations EφE^t=φ^′, where φ, φ^′ are alternating matrices of Pfaffian 1, which at most differ in their first row and column, and E is of the form . If v, v^′, w∈R^r+1 with 〈v,w〉=1=〈v^′,w〉 then a sequence of Cohn transforms with respect to (the fixed) w which takes (v,w) to (v^′,w) is prescribed.     

Simple image set of linear mappings in a max-min algebra

For a given linear mapping, determined by a square matrix A in a max-min algebra, the set S_A consisting of all vectors with a unique pre-image (in short: the simple image set of A) is considered. It is shown that if the matrix A is generally trapezoidal, then the closure of S_A is a subset of the set of all eigenvectors of A. In the general case, there is a permutation π, such that the closure of S_A is a subset of the set of all eigenvectors permuted by π. The simple image set of the matrix square and the topological aspects of the problem are also described.     

A relation between the comparability graph and the number of linear extensions

In this note, we prove that the comparability graph of a posetP has less edges than that of a posetQ on the same set of elements, thenP has more linear extensions thanQ. This solves a problem posed by Kelly [1].Research partially supported by the grant RP.I.09 from the Institute of Informatics, University of Warsaw.     

A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders

Let L=u ₁ , u ₂ , ..., u _k be a linear extension of a poset P. Each pair (u _i , u _i+1 ) of unrelated elements in P is called a jump of L. The jump number problem is to find L with the minimum number of jumps. The problem is known to be NP-hard even on bipartite posets. Here we present a linear time algorithm for it in 2-dimensional bipartite posets. We also discuss briefly some weighted cases.     

On computing the number of linear extensions of a tree

An algorithm requiring O(n ²) arithmetic operations for computing the number of linear extensions of a poset whose covering graph is a tree is given.This research was partially funded by the National Science and Engineering Research Council of Canada under Grant Number A4219.     

Weakly linear quantum MV-algebras

Quantum MV-algebras (QMV-algebras) are a non lattice-theoretic generalization of MV-algebras (multi-valued algebras) and a non-idempotent generalization of orthomodular lattices. In this paper we construct a finite basis for the variety generated by the class of all weakly linear quantum MV-algebras.Dedicated to the memory of Wim BlokReceived October 12, 2000; accepted in final form October 3, 2004.This revised version was published online in August 2005 with a corrected cover date.     

Nowhere dense set mappings on the generalized linear continua

A set is free for a set mapping F:XP(X) provided xF(y) for any distinct x, y in A. If F maps the reals R into nowhere dense subsets of R, then Bagemihl proved that there is an everywhere dense free set for F, and assuming CH Hechler showed that such an F does not always admit an uncountable free set. In this paper, we show that Bagemihl's theorem cannot be generalized to the generalized linear continua C for arbitrarily large ordinal , and under GCH we extend Hechler's theorem to C for every .     

On minimizing jumps for ordered sets

An ordered set P is called K-free if it does not contain a four-element subset {a, b, c, d} such that a < b is the only comparability among these elements. In this paper we present a polynomial algorithm to find the jump number of K-free ordered sets.     

On finding the jump number of a partial orber by substitution decomposition

Consider the linear extensions of a partial order. A jump occurs in a linear extension if two consecutive elements are unrelated in the partial order. The jump number problem is to find a linear extension of the ordered set which contains the smallest possible number of jumps. We discuss a decomposition approach for this problem from an algorithmic point of view. Based on this some new classes of partial orders are identified, for which the problem is polynomially solvable.     

Asymptotic preconditioning of linear homogeneous systems of differential equations

We consider the asymptotic behavior of solutions of a linear differential system x^′=A(t)x, where A is continuous on an interval ([a,∞). We are interested in the situation where the system may not have a desirable asymptotic property such as stability, strict stability, uniform stability, or linear asymptotic equilibrium, but its solutions can be written as x=Pu, where P is continuously differentiable on [a,∞) and u is a solution of a system u^′=B(t)u that has the property in question. In this case we say that P preconditions the given system for the property in question.     

On the number of k-realizations of an ordered set

A k-realization of an ordered set P is a sequence of k linear orderings of the underlying set of P, whose intersection is (the order relation of) P. We determine the status of the number of k-realizations with respect to comparability invariance, and we show that among all orders on the set {1, 2, ..., n}, the antichain has the most k-realizations, for any k>1. The latter intuitively reasonable result rests ultimately on an observation related to comparability invariance for numbers of linear extensions.Research supported by ONR Contract N00014 85-K-0769.