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.     

Seminorms on ordered vector spaces that extend to Riesz seminorms on larger Riesz spaces

As a generalization of the notion of Riesz seminorm, a class of seminorms on directed partially ordered vector spaces is introduced, such that (1) every seminorm in the class can be extended to a Riesz seminorm on every larger Riesz space that is majorized and (2) a seminorm on an order dense linear subspace of a Riesz space is in the class if and only if it can be extended to a Riesz seminorm on the Riesz space. The latter property yields that if a directed partially ordered vector space has an appropriate Riesz completion, then a seminorm on the space is in the class if and only if it is the restriction of a Riesz seminorm on the Riesz completion. An explicit formula for the extension is given. The class of seminorms is described by means of a notion of solid unit ball in partially ordered vector spaces. Some more properties concerning restriction and extension are studied, including extension to L- and M-seminorms.     

Constructing greedy linear extensions by interchanging chains

A natural way to prove that a particular linear extension of an ordered set is ‘optimal’ with respect to the ‘jump number’ is to transform this linear extension ‘canonically’ into one that is ‘optimal’. We treat a ‘greedy chain interchange’ transformation which has applications to ordered sets for which each ‘greedy’ linear extension is ‘optimal’.     

Unboundedness in Integer and Discrete Programming L.P. Relaxations

Commercial branch and bound codes for solving the general mixed integer linear programming problem commence by solving the linear programming relaxation of the submitted problem, terminating if the relaxation is unbounded. It is assumed that the submitted problem is either unbounded or has no feasible solutions. It is shown that the assumption is correct for all integer programming problems which can be submitted to the currently available codes (though counter examples which cannot be so submitted are given), but that the assumption is generally incorrect for discrete linear programming problems (using for example the special ordered set construct). Sufficient conditions on formulations to ensure its correctness are given. One possible formulation approach, applicable to special ordered set situations, is discussed.     

Games with Ordered Outcomes

We present a brief review of the most important concepts and results concerning games in which the goal structure is formalized by binary relations called preference relations. The main part of the work is devoted to games with ordered outcomes, i.e., game-theoretic models in which preference relations of players are given by partial orders on the set of outcomes. We discuss both antagonistic games and n-person games with ordered outcomes. Optimal solutions in games with ordered outcomes are strategies of players, situations, or outcomes of the game. In the paper, we consider noncooperative and certain cooperative solutions. Special attention is paid to an extension of the order on the set of probabilistic measures since this question is substantial for constructing the mixed extension of the game with ordered outcomes. The review covers works published from 1953 until now.     

NP-Completeness results concerning greedy and super greedy linear extensions

Various problems concerning greedy and super greedy linear extensions are shown to be NP-complete. In particular, the problem, due to Cogis, of determining that an ordered set is not greedy is NP-complete, as is the problem, due to Rival and Zaguia, of determining whether an ordered set has a greedy linear extension, which satisfies certain additional constraints. The author was supported in part by ONR grant N00014-85K-0494 and NSERC grants 69-3378. 69-0259, and 69-1325.     

Maximal and Minimal Semilattices on Ordered Sets

The map which takes an element of an ordered set to its principal ideal is a natural embedding of that ordered set into its powerset, a semilattice. If attention is restricted to all finite intersections of the principal ideals of the original ordered set, then an embedding into a much smaller semilattice is obtained. In this paper the question is answered of when this construction is, in a certain arrow-theoretic sense, minimal. Specifically, a characterisation is given, in terms of ideals and filters, of those ordered sets which admit a so-called minimal embedding into a semilattice. Similarly, a candidate maximal semilattice on an ordered set can be constructed from the principal filters of its elements. A characterisation of those ordered sets that extend to a maximal semilattice is given. Finally, the notion of a free semilattice on an ordered set is given, and it is shown that the candidate maximal semilattice in the embedding-theoretic sense is the free object.     

Structural stability via the density of a class of linear discrete systems

In this paper we prove that the set of multiplicatively separated linear discrete systems is dense in the set of linear systems and we find a relationship between the set of structurally stable systems and the set of the systems which have an exponential dichotomy.     

Extension conditions for bounded linear and sublinear operators with values in lindenstrauss spaces

We find extension conditions for linear and sublinear operators with values in four classes of spaces: the spaces of continuous functions on a compact set, Lindenstrauss spaces, and their separable parts. We prove that in all these cases the extension property for linear operators implies the extension property for sublinear operators, while in separable spaces the two properties are equivalent.     

Extendability of Cyclic Orders

A cyclic order is a ternary relation that satisfies ternary transitivity and asymmetry conditions. Such a ternary relation is extendable if it is included in a complete cyclic order on the same ground set. Unlike the case of linear extensions of partial orders, a cyclic order need not be extendable. The extension problem for cyclic orders is to determine if a cyclic order is extendable. This problem is known to be NP-complete. We introduce a class of cyclic orders in which the extension problem can be solved in polynomial time. The class provides many explicit examples of nonextendable cyclic orders that were not previously known, including a nonextendable cyclic order on seven points. Let μ be the maximum cardinality of a ground set on which all cyclic orders are extendable. It has been shown that μ≤9. We prove that μ=6. This answers a question of Novák. In addition, we characterize the nonextendable cyclic orders on seven and eight points. Our results are intimately related to irreducible partially ordered set of order dimension three, and to fractional vertices of generalized transitive tournament polytopes. As by-products, we obtain a characterization of cyclically ordered sets of dimension two, and a new proof of a theorem of Dridi on small linear ordering polytopes. This revised version was published online in June 2006 with corrections to the Cover Date.     

Topological properties of definable sets in ordered Abelian groups of burden 2

We obtain some new results on the topology of unary definable sets in expansions of densely ordered Abelian groups of burden 2. In the special case in which the structure has dp-rank 2, we show that the existence of an infinite definable discrete set precludes the definability of a set which is dense and codense in an interval, or of a set which is topologically like the Cantor middle-third set (Theorem 2.9). If it has burden 2 and both an infinite discrete set D and a dense-codense set X are definable, then translates of X must witness the Independence Property (Theorem 2.26). In the last section, an explicit example of an ordered Abelian group of burden 2 is given in which both an infinite discrete set and a dense-codense set are definable.     

Typical curvature behaviour of bodies of constant width

It is known that an n-dimensional convex body, which is typical in the sense of Baire category, shows a simple, but highly non-intuitive curvature behaviour: at almost all of its boundary points, in the sense of measure, all curvatures are zero, but there is also a dense and uncountable set of boundary points at which all curvatures are infinite. The purpose of this paper is to find a counterpart to this phenomenon for typical convex bodies of given constant width. Such bodies cannot have zero curvatures. A main result says that for a typical n-dimensional convex body of constant width 1 (without loss of generality), at almost all boundary points, in the sense of measure, all curvatures are equal to 1. (In contrast, note that a ball of width 1 has radius 1/2, hence all its curvatures are equal to 2.) Since the property of constant width is linear with respect to Minkowski addition, the proof requires recourse to a linear curvature notion, which is provided by the tangential radii of curvature.     

Ideals and bands in pre-Riesz spaces

In a vector lattice, ideals and bands are well-investigated subjects. We study similar notions in a pre-Riesz space. The pre-Riesz spaces are exactly the order dense linear subspaces of vector lattices. Restriction and extension properties of ideals, solvex ideals and bands are investigated. Since every Archimedean directed partially ordered vector space is pre-Riesz, we establish properties of ideals and bands in such spaces.      

Extension theorems for linear lattices with positive algebraic basis

An ordered linear spaceV with positive wedgeK is said to satisfy extension property (E1) if for every subspaceL ₀ ofV such thatL ₀ ∩K is reproducing inL ₀, and every monotone linear functionalf ₀ defined onL ₀,f ₀ has a monotone linear extension to all ofV. A linear latticeX is said to satisfy extension property (E2) if for every sublatticeL ofX, and every linear functionalf defined onL which is a lattice homomorphism,f has an extensionf′ to all ofX which is also a linear functional and a lattice homomorphism. In this paper it is shown that a linear lattice with a positive algebraic basis has both extension property (E1) and (E2). In obtaining this result it is shown that the linear span of a lattice idealL and an extremal element not inL is again a lattice ideal. (HereX does not have to have a positive algebraic basis.) It is also shown that a linear lattice which possesses property (E2) must be linearly and lattice isomorphic to a functional lattice. An example is given of a function lattice which has property (E2) but does not have a positive algebraic basis. Yudin [12] has shown a reproducing cone in ann-dimensional linear lattice to be the intersection of exactlyn half-spaces. Here it is shown that the positive wedge in ann-dimensional archimedean ordered linear space satisfying the Riesz decomposition property must be the intersection ofn half-spaces, and hence the space must be a linear lattice with a positive algebraic basis. The proof differs from those given for the linear lattice case in that it uses no special techniques, only well known results from the theory of ordered linear space.     

A Brézis-Browder principle on partially ordered spaces and related ordering theorems

Through a simple extension of Brézis-Browder principle to partially ordered spaces, a very general strong minimal point existence theorem on quasi ordered spaces, is proved. This theorem together with a generic quasi order and a new notion of strong approximate solution allow us to obtain two strong solution existence theorems, and three general Ekeland variational principles in optimization problems where the objective space is quasi ordered. Then, they are applied to prove strong minimal point existence results, generalizations of Bishop-Phelps lemma in linear spaces, and Ekeland variational principles in set-valued optimization problems through a set solution criterion.     

QUantale中的闭滤子

在Quantale中讨论了与Gabriel拓扑密切关联的闭滤子,给出了闭滤子与闭映射之间的相互确定关系．证明了凝聚左侧Quantale Q的闭滤子全体F(Q)在包含序下构成Frame,并且Q的紧闭滤子全体Fc(Q)是F(Q)的子Frame．最后,证明了凝聚双侧交换Quantale的紧闭滤子全体在包含序下构成Coherent Frame．     

Convex extensions of the convex set valued maps

In this article the existence of the convex extension of convex set valued map is considered. Conditions are obtained, based on the notion of the derivative of set valued maps, which guarantee the existence of convex extension. The conditions are given, when the convex set valued map has no convex extension. The convex set valued map is specified, which is the maximal convex extension of the given convex set valued map and includes all other convex extensions. The connection between Lipschitz continuity and existence of convex extension of the given convex set valued map is studied.     

Linear Orders on General Algebras

We answer the question, when a partial order in a partially ordered algebraic structure has a compatible linear extension. The finite extension property enables us to show, that if there is no such extension, then it is caused by a certain finite subset in the direct square of the base set. As a consequence, we prove that a partial order can be linearly extended if and only if it can be linearly extended on every finitely generated subalgebra. Using a special equivalence relation on the above direct square, we obtain a further property of linearly extendible partial orders. Imposing conditions on the lattice of compatible quasi orders, the number of linear orders can be determined. Our general approach yields new results even in the case of semi-groups and groups.     

Congruence-preserving functions on Stone and Kleene algebras

We investigate local polynomial functions on Stone algebras and on Kleene algebras. We find a generating set for the clone of all local polynomial functions. We also represent local polynomial functions on a given algebra by polynomial functions of some canonical extension of this algebra.