Chain Dominated Orders

We study finite partial orders which have a chain such that every element of the order either belongs to this chain or has all its covers in this chain. We show that such orders are exactly the orders being both interval orders and truncated lattices. We prove that their jump number is polynomially tractable and that their dimension is unbounded. We also show that every order admits a visibility model having such an order as host.     

Numerical Representations of Interval Orders

In the framework of the analysis of orderings whose associated indifference relation is not necessarily transitive, we study the structure of an interval order and its representability through a pair of real-valued functions. We obtain a list of characterizations of the existence of a representation, showing that the three main techniques that have been used in the literature to achieve numerical representations of interval orders are indeed equivalent.     

Epimorphisms Between Linear Orders

We study the relation on linear orders induced by order preserving surjections. In particular we show that its restriction to countable orders is a bqo.     

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.     

Fountain-Gould Left Orders for Associative Pairs

In this paper, we introduce a notion of weak Fountain-Gould left order for associative pairs and give a Goldie-like theory of associative pairs which are weak Fountain Gould left orders in semiprime pairs coinciding with their socles.     

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.     

Combinatorial Aspects of Total Weight Orders over Monomials of Fixed Degree

Among all the restrictions of weight orders to the subsets of monomials with a fixed degree, we consider those that yield a total order. Furthermore, we assume that each weight vector consists of an increasing tuple of weights. Every restriction, which is shown to be achieved by some monomial order, is interpreted as a suitable linearization of the poset arising by the intersection of all the weight orders. In the case of three variables, an enumeration is provided. For a higher number of variables, we show a necessary condition for obtaining such restrictions, using deducibility rules applied to homogeneous inequalities. The logarithmic version of this approach is deeply related to classical results of Farkas type, on systems of linear inequalities. Finally, we analyze the linearizations determined by sequences of prime numbers and provide some connections with topics in arithmetic.     

Segment Orders

We study two kinds of segment orders, using definitions first proposed by Farhad Shahrokhi. Although the two kinds of segment orders appear to be quite different, we prove several results suggesting that the are very much the same. For example, we show that the following classes belong to both kinds of segment orders: (1) all posets having dimension at most 3; (2) interval orders; and for n≥3, the standard example S _n of an n-dimensional poset, all 1-element and (n−1)-element subsets of {1,2,…,n}, partially ordered by inclusion. Moreover, we also show that, for each d≥4, almost all posets having dimension d belong to neither kind of segment orders. Motivated by these observations, it is natural to ask whether the two kinds of segment orders are distinct. This problem is apparently very difficult, and we have not been able to resolve it completely. The principal thrust of this paper is the development of techniques and results concerning the properties that must hold, should the two kinds of segment orders prove to be the same. We also derive equivalent statements, one version of which is a stretchability question involving certain sets of pseudoline arrangements. We conclude by proving several facts about continuous universal functions that would transfer segment orders of the first kind into segments orders of the second kind.     

On the Ferrers property of valued interval orders

We study the relationship between the Ferrers property and the notion of interval order in the context of valued relations. Given a crisp preference structure without incomparability, the strict preference relation satisfies the Ferrers property if and only if the associated weak preference relation does. These conditions characterize a total interval order. For valued relations the Ferrers property can be written in two different and non-equivalent ways. In this work, we compare these properties by finding the kind of completeness they imply. Moreover, we study whether they still characterize a valued total interval orders.     

Almost Connected Orders

One of the standard axioms for semiorders states that no three-point chain is incomparable to a fourth point. We refer to asymmetric relations satisfying this axiom as almost connected orders or ac-orders. It turns out that any relation lying between two weak orders, one of which covers the other for inclusion, is an ac-order (albeit of a special kind). Every ac-order is bracketed in a natural way by two weak orders, one the maximum in the set of weak orders included in the ac-order, and the other minimal, but not necessarily the minimum, in the set of weak orders that include the ac-order. The family of ac-orders on a finite set with at least five elements is not well graded (in the sense of Doignon and Falmagne, 1997). However, such a family is both upgradable and downgradable, as every nonempty ac-order contains a pair whose deletion defines an ac-order on the same set, and for every ac-order which is not a chain, there is a pair whose addition gives an ac-order.     

Counting Endomorphisms of Crown-like Orders

The authors introduce the notion of crown-like orders and introduce powerful tools for counting the endomorphisms of orders of this type.     

Linear Extensions of Additive Partial Orders

Addive partial orders arise naturally in theories of comparativeprobability and subset preferences. An additive partial order is a partialorder on the family of subsets of ann-element set that satisfies . This is reformulated as a subset P of {1,0,–1}ⁿ that excludes 0 and containsx+y whenever x,y P and x+y {1,0,–1}ⁿ. Additional conditions of positivity andcompleteness give rise to positive additive partial orders and additivelinear orders respectively. The paper investigates conditions under which anadditive partial order is included in, or extendable to, an additive linearorder. The additive dimension of an extendable additive partial order isdefined and computed for several classes of additive orders.     

Choiceless Ramsey Theory of Linear Orders

Motivated by work of Erd?s, Milner and Rado, we investigate symmetric and asymmetric partition relations for linear orders without the axiom of choice. The relations state the existence of a subset in one of finitely many given order types that is homogeneous for a given colouring of the finite subsets of a fixed size of a linear order. We mainly study the linear orders 〈 ^α 2,< _{l e x} 〉, where α is an infinite ordinal and < _{l e x} is the lexicographical order. We first obtain the consistency of several partition relations that are incompatible with the axiom of choice. For instance we derive partition relations for 〈 ^ω 2,< _{l e x} 〉 from the property of Baire for all subsets of ^ω 2 and show that the relation \(\langle ^{\kappa }{2}, <_{lex}\rangle \longrightarrow (\langle ^{\kappa }{2}, <_{lex}\rangle )^{2}_{2}\) is consistent for uncountable regular cardinals κ with κ ^<κ = κ. We then prove a series of negative partition relations with finite exponents for the linear orders 〈 ^α 2,< _{l e x} 〉. We combine the positive and negative results to completely classify which of the partition relations \(\langle ^{\omega }{2}, <_{lex}\rangle \longrightarrow (\bigvee _{\nu <\lambda }K_{\nu },\bigvee _{\nu <\mu }M_{\nu })^{m}\) for linear orders K _ν ,M _ν and m≤4 and 〈 ^ω 2,< _{l e x} 〉→(K,M) ⁿ for linear orders K,M and natural numbers n are consistent.     

富足半群上的自然偏序

本文研究富足半群上的自然偏序，得到Green关系和自然偏序之间的联系，确定了富足半群何时关于自然偏序具有单边(双边)相容，另外，也研究了富足半群的本原元。     

Transitive Oriented 3 Hypergraphs of Cyclic Orders

In this paper we introduce the definition of transitivity for oriented 3-hypergraphs in order to study partial and complete cyclic orders. This definition allows us to give sufficient conditions on a partial cyclic order to be totally extendable. Furthermore, we introduce the 3-hypergraph associated to a cyclic permutation and characterize it in terms of cyclic comparability 3-hypergraphs.     

Normalized Matching in Direct Products of Partial Orders

In this paper we investigate the question: When does the direct product of partial orders each satisfying the normalized matching condition also satisfy it? A proof of Harper's result that a sufficient condition for this is that factor partial orders have rank populations that are multiplicatively convex, is presented. A general necessary and sufficient condition is described, and conditions which occur when one factor is a chain are obtained. In particular we show that under these circumstances it is necessary that the product order have multiplicatively convex population rank.     

Maximal Orders In Completely 0-simple Semigroups

Fountain, Gould and Smith introduced the concept of equivalence of orders in a semigroup and the notion of a maximal order. We examine these ideas in the context of orders in completely 0-simple semigroups with particular emphasis on abundant orders.     

Scheduling of corrugated paper production

Corrugated paper is produced by gluing three types of papers of the same breadth. Given a set of orders, we first assign each order to one of the standard breadths, and then sequence those assigned to each standard breadth so that they are continuously manufactured from the three rolls of the specified standard breadth equipped in the machine called corrugator. Here we are asked to achieve multi-goals of minimizing total length of roll papers, total loss of papers caused by the differences between standard breadths and real breadths of the orders, and the number of machine stops needed during production. We use integer programming to assign orders to standard breadths, and then develop a special purpose algorithm to sequence the orders assigned to each standard breadth. This is a first attempt to handle scheduling problems of the corrugator machine.     

Unit and Proper Tube Orders

In 2005, we defined the n-tube orders, which are the n-dimensional analogue of interval orders in 1 dimension, and trapezoid orders in 2 dimensions. In this paper we consider two variations of n-tube orders: unit n-tube orders and proper n-tube orders. It has been proven that the classes of unit and proper interval orders are equal, and the classes of unit and proper trapezoid orders are not. We prove that the classes of unit and proper n-tube orders are not equal for all n ≥ 3, so the general case follows the situation in 2 dimensions.     

Generalized Growth Orders for Polymonogenic Functions and Related Inequalities

In this paper we introduce generalized growth orders and growth types in the sense of Shah and Seremeta in the context of polymonogenic functions. They provide a refinement of previously introduced growth orders in the study of the asymptotic growth behavior of functions satisfying higher dimensional Cauchy–Riemann type equations. We prove a number of insight giving inequalities and manage to extend some basic results that were recently proved for the context of the usual first order Cauchy–Riemann system in Clifford analysis.