Lexicographic effect algebras

We investigate a class of effect algebras that can be represented in the form \({\Gamma (H \overrightarrow{\times} G}\), (u, 0)), where \({H \overrightarrow{\times} G}\) means the lexicographic product of an Abelian unital po-group (H, u) and an Abelian directed po-group G. We study conditions when an effect algebra is of this form. Fixing a unital po-group (H, u), the category of strongly (H, u)-perfect effect algebras is introduced and it is shown that it is categorically equivalent to the category of directed po-groups with interpolation. We prove some representation theorems of lexicographic effect algebras, including a subdirect product representation by antilattice lexicographic effect algebras.     

Lexicographic TAF Algebras

Lexicographic TAF algebras constitute a class of triangular AF
algebras which are determined by a countable ordered set , a dimension function, and a third parameter. While some of the important examples of TAF algebras belong to the class, most algebras in this class have not been studied. The semigroupoid of the algebra, the lattice of invariant projections, the Jacobson radical, and for some cases the automorphism group are computed. Necessary and sufficient conditions for analyticity are given. The results often involve the order properties of the set .

     

Representable Lexicographic Products

A linear ordering is said to be representable if it can be order-embedded into the reals. Representable linear orderings have been characterized as those which are separable in the order topology and have at most countably many jumps. We use this characterization to study the representability of a lexicographic product of linear orderings. First we count the jumps in a lexicographic product in terms of the number of jumps in its factors. Then we relate the separability of a lexicographic product to properties of its factors, and derive a classification of representable lexicographic products. This revised version was published online in September 2006 with corrections to the Cover Date.     

Lexicographic quasiconcave multiobjective programming

Summary Letf _i :A R ben real-valued objective functions on a convex setA -K ^m ,K:=R orC, n, mN. Letg: A R ⁿ be defined by , where for eachxA, (i ₁ (x), ..., i _n (x)) is a permutation of (1, ...,n) such that . In this paper we treat the problem of findingx ^*A such that , wherel-max denotes the lexicographic maximum. If the f_i's are strongly quasiconcave we can reduce the problem stepwise until finally it is in the form of a scalar programming problem. Further, we consider conditions for the existence and uniqueness of a solution and discuss the relationship of the problem to the vector maximum (i.e. Pareto) and maxmin (i.e. Chebychev) problems.

---

Zusammenfassung f _i :AR seienn reellwertige Zielfunktionen über einer konvexen MengeA-K ^m ,K:=R oderC, n, mN. g:AR ⁿ sei definiert durch , wobei für jedesxA (i ₁ (x), ... i _n (x)) eine Permutation von (1, ...,n) derart ist, daß Wir betrachten das Problem, einx ^*A so zu finden, daß , wobeil-max das lexikographische Maximum bedeute. Falls dief _i stark quasikonkav sind, läßt sich das Problem stufenweise reduzieren, bis es schließlich die Gestalt eines skalaren Optimierungsproblems annimmt. Wir geben Existenz- und Eindeutigkeitsbedingungen an und besprechen Zusammenhänge mit dem Vektormaximumproblem (d.h. Pareto-Optimierung) und dem Maxmin-Problem (d.h. Tschebyscheff-Optimierung).

     

Lexicographic balanced optimization problems

We introduce the lexicographic balanced optimization problem (LBaOP) and show that it can be solved efficiently if an associated lexicographic bottleneck problem can be solved efficiently. For special cases of cuts in a graph and base system of a matroid, improved algorithms are proposed. A generalization of LBaOP is also discussed.     

Lexicographic behaviour of chains

This paper introduces a different approach to the study of the existence of numerical representations of totally ordered sets (chains). We pay attention to the properties of non-representable chains showing that, under certain conditions, those chains must have a sort of lexicographic behaviour similar to that of the lexicographic plane. We prove that a countably bounded connected chain (Z, \prec )(Z, \prec ) admits a lexicographic decomposition as a subset of the lexicographic product \Bbb R ×Z\Bbb R \times Z. Then we apply our approach to state both a sufficient and a necessary condition for the lack of utility functions. The concept of planar chain is also introduced.     

Lexicographic Order and Linearity

Let be a list of all words of , lexicographically ordered with respect to some basis. Lexicodes are codes constructed from by applying a greedy algorithm. A short proof, only based on simple principles from linear algebra, is given for the linearity of these codes. The proof holds for any ordered basis, and for any selection criterion, thus generalizing the results of several authors. An extension of the applied technique shows that lexicodes over are linear for a wide choice of bases and for a large class of selection criteria. This result generalizes a property of Conway and Sloane.     

Pointwise Debreu Lexicographic Powers

A linear ordering is Debreu (respectively, pointwise Debreu) if each of its suborderings can be mapped into it with an order-preserving function that is both injective (respectively, locally injective) and continuous (respectively, locally continuous) with respect to the order topology on both spaces. Each Debreu linear ordering is pointwise Debreu, but the converse does not hold. In the context of utility representations in mathematical economics, it has been proved that any lexicographic power with an uncountable exponent fails to be Debreu. We sharpen this result by analyzing lexicographic powers that are pointwise Debreu.     

Lexicographic generation of projective spaces

Lexicographic or first choice constructions of geometric objects sometimes lead to amazingly good results. Usually it is difficult to determine the precise identity of the resulting geometries. Here we find infinitely many cases where the identification actually can be accomplished.     

Discrete and Lexicographic Helly-Type Theorems

Helly’s theorem says that if every d+1 elements of a given finite set of convex objects in ℝ ^d have a common point, then there is a point common to all of the objects in the set. We define three new types of Helly theorems: discrete Helly theorems—where the common point should belong to an a-priori given set, lexicographic Helly theorems—where the common point should not be lexicographically greater than a given point, and lexicographic-discrete Helly theorems. We study the relations between the different types of the Helly theorems. We obtain several new discrete and lexicographic Helly numbers. An extended abstract containing parts of this work appeared in the proceedings of the Forty-Fifth Annual Symposium on Foundations of Computer Science (FOCS) 2004. This work is part of the author’s Ph.D. thesis, prepared in the school of mathematical sciences at Tel Aviv University, under the supervision of Professor Arie Tamir.     

Lexicographic differentiation of nonsmooth functions

We present a survey on the results related to the theory of lexicographic differentiation. This theory ensures an efficient computation of generalized (lexicographic) derivative of a nonsmooth function belonging to a special class of lexicographically smooth functions. This class is a linear space which contains all differentiable functions, all convex functions, and which is closed with respect to component-wise composition of the members. In order to define lexicographic derivative in a unique way, it is enough to fix a basis in the space of variables. Lexicographic derivatives can be used in black-box optimization methods. We give some examples of applications of these derivatives in analysis of nonsmooth functions. It is shown that the system of lexicographic derivatives along a fixed basis correctly represents corresponding nonsmooth function (Newton-Leibnitz formula). We present nonsmooth versions of standard theorems on potentiality of nonlinear operators, on differentiation of parametric integrals and on differentiation of functional sequences. Finally, we show that an appropriately defined lexicographic subdifferential ensures a more rigorous selection of a candidate optimal solution than the subdifferential of Clarke. Dedicated to R. T. Rockafellar on his 70th birthday. This paper presents research results of the Belgian Program on Interuniversity Attraction Poles, initiated by the Belgian Federal Science Policy Office. The scientific responsibility rests with its author.     

Lexicographic compositions and deBruijn sequences

In this paper we give an algorithm to generate a new deBruijn sequence. The amount of storage required is only linear in n, the span of the sequence. We make use of the lexicographic compositions of a positive integer which we relate to binary necklaces of beads in two colors. We give a fast algorithm for generating the necklaces. Finally we relate the deBruijn sequence we generate to another sequence.     

Lexicographic variational inequalities with applications

In this article, we consider equivalence properties between various kinds of lexicographic variational inequalities. By employing various concepts of monotonicity, we show that the usual sequential variational inequality is equivalent to the direct lexicographic variational inequality or to the dual lexicographic variational inequality. We establish several existence results for lexicographic variational inequalities. Also, we introduce the lexicographic complementarity problem and establish its equivalence with the lexicographic variational inequality. We illustrate our approach by several examples of applications to vector transportation and vector spatial equilibrium problems.     

Lexicographic and sequential equilibrium problems

The aim of this work is to analyze lexicographic equilibrium problems on a topological Hausdorff vector space X, and their relationship with some other vector equilibrium problems. Existence results for the tangled lexicographic problem are proved via the study of a related sequential problem. This approach was already followed by the same authors in the case of variational inequalities.     

Quotient Complexes and Lexicographic Shellability

Let _n,k,k and _n,k,h , h < k, denote the intersection lattices of the k-equal subspace arrangement of type _n and the k,h-equal subspace arrangement of type _n respectively. Denote by the group of signed permutations. We show that ( _n,k,k )/ is collapsible. For ( _n,k,h )/ , h < k, we show the following. If n 0 (mod k), then it is homotopy equivalent to a sphere of dimension . If n h (mod k), then it is homotopy equivalent to a sphere of dimension . Otherwise, it is contractible. Immediate consequences for the multiplicity of the trivial characters in the representations of on the homology groups of ( _n,k,k ) and ( _n,k,h ) are stated.The collapsibility of ( _n,k,k )/ is established using a discrete Morse function. The same method is used to show that ( _n,k,h )/ , h < k, is homotopy equivalent to a certain subcomplex. The homotopy type of this subcomplex is calculated by showing that it is shellable. To do this, we are led to introduce a lexicographic shelling condition for balanced cell complexes of boolean type. This extends to the non-pure case work of P. Hersh (Preprint, 2001) and specializes to the CL-shellability of A. Björner and M. Wachs (Trans. Amer. Math. Soc. 4 (1996), 1299–1327) when the cell complex is an order complex of a poset.     

Lexicographic sums and fibre-faithful maps

The notion of lexicographic sum is introduced in general categories. Existence criteria are derived, particularly for locally cartesian closed categories and for categories with suitable coproducts. Lexicographic sums satisfy a generalized associative law. More importantly, every morphism can be factored through the lexicographic sum of its fibres. This factorization and the two types of maps arising from it, fibre-trivial and fibre-faithful, are studied particularly for partially ordered sets and forT ₁-spaces.