Uniquely orderable interval graphs

Interval graphs and interval orders are deeply linked. In fact, edges of an interval graphs represent the incomparability relation of an interval order, and in general, of different interval orders. The question about the conditions under which a given interval graph is associated to a unique interval order (up to duality) arises naturally. Fishburn provided a characterisation for uniquely orderable finite connected interval graphs. We show, by an entirely new proof, that the same characterisation holds also for infinite connected interval graphs. Using tools from reverse mathematics, we explain why the characterisation cannot be lifted from the finite to the infinite by compactness, as it often happens.     

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.     

Proper and Unit Trapezoid Orders and Graphs

We show that the class of trapezoid orders in which no trapezoid strictly contains any other trapezoid strictly contains the class of trapezoid orders in which every trapezoid can be drawn with unit area. This is different from the case of interval orders, where the class of proper interval orders is exactly the same as the class of unit interval orders.     

Inductive Characterizations of Finite Interval Orders and Semiorders

We introduce an inductive definition for two classes of orders. By simple proofs, we show that one corresponds to the interval orders class and that the other is exactly the semiorders class.     

An upper bound on the “dimension of interval orders”

The main results of this paper are two distinct characterizations of interval orders and an upper bound on the dimension of an interval order as a function of its height. In particular, interval orders of height 1 have dimension of at most 2.     

N-free orders and minimal interval extensions

We investigate problems related to the set of minimal interval extensions of N-free orders. This leads us to a correspondence between this set for an arbitrary order and a certain set of its maximal N-free reductions. We also get a 1-1-correspondence between the set of linear extensions of an arbitrary order and the set of minimal interval extensions of the linegraph of that order. This has an algorithmic consequence, namely the problem of counting minimal interval extensions of an N-free order is #P-complete. Finally a characterization of all N-free orders with isomorphic root graph is given in terms of their lattice of maximal antichains; the lattices are isomorphic iff the root graphs agree.This work was supported by the PROCOPE Program. The first author is supported by the DFG.     

Obstructions to Shellability

We consider a simplicial complex generalization of a result of Billera and Myers that every nonshellable poset contains the smallest nonshellable poset as an induced subposet. We prove that every nonshellable two-dimensional simplicial complex contains a nonshellable induced subcomplex with less than eight vertices. We also establish CL-shellability of interval orders and as a consequence obtain a formula for the Betti numbers of any interval order. Received August 7, 1997, and in revised form September 9, 1998.     

Optimal preemptive scheduling on a fixed number of identical parallel machines

In this paper, we consider the preemptive scheduling problem on a fixed number of identical parallel machines. We present a polynomial-time algorithm for finding a minimal length schedule for an order class which contains properly interval orders.     

Optimal scheduling on parallel machines for a new order class

This paper addresses the problem of scheduling n unit length tasks on m identical machines under certain precedence constraints. The aim is to compute minimal length nonpreemptive schedules. We introduce a new order class which contains properly two rich families of precedence graphs: interval orders and a subclass of the class of series parallel orders. We present a linear time algorithm to find an optimal schedule for this new order class on any number of machines.     

Interval Reductions and Extensions of Orders: Bijections to Chains in Lattices

We discuss bijections that relate families of chains in lattices associated to an order P and families of interval orders defined on the ground set of P. Two bijections of this type have been known:(1) The bijection between maximal chains in the antichain lattice A(P) and the linear extensions of P.(2) The bijection between maximal chains in the lattice of maximal antichains A_M(P) and minimal interval extensions of P.We discuss two approaches to associate interval orders with chains in A(P). This leads to new bijections generalizing Bijections 1 and 2. As a consequence, we characterize the chains corresponding to weak-order extensions and minimal weak-order extensions of P.Seeking for a way of representing interval reductions of P by chains we came upon the separation lattice S(P). Chains in this lattice encode an interesting subclass of interval reductions of P. Let S_M(P) be the lattice of maximal separations in the separation lattice. Restricted to maximal separations, the above bijection specializes to a bijection which nicely complements 1 and 2.(3) A bijection between maximal chains in the lattice of maximal separations S_M(P) and minimal interval reductions of P.     

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.     

Counting general and self-dual interval orders

In this paper, we present a new method to derive formulas for the generating functions of interval orders, counted with respect to their size, magnitude, and number of minimal and maximal elements. Our method allows us not only to generalize previous results on refined enumeration of general interval orders, but also to enumerate self-dual interval orders with respect to analogous statistics.Using the newly derived generating function formulas, we are able to prove a bijective relationship between self-dual interval orders and upper-triangular matrices with no zero rows. Previously, a similar bijective relationship has been established between general interval orders and upper-triangular matrices with no zero rows and columns.     

Interval <Emphasis Type="Italic">k</Emphasis>-Graphs and Orders

An interval k-graph is the intersection graph of a family of intervals of the real line partitioned into k classes with vertices adjacent if and only if their corresponding intervals intersect and belong to different classes. In this paper we study the cocomparability interval k-graphs; that is, the interval k-graphs whose complements have a transitive orientation and are therefore the incomparability graphs of strict partial orders. For brevity we call these orders interval k-orders. We characterize the kind of interval representations a cocomparability interval k-graph must have, and identify the structure that guarantees an order is an interval k-order. The case k =?2 is peculiar: cocomparability interval 2-graphs (equivalently proper- or unit-interval bigraphs, bipartite permutation graphs, and complements of proper circular-arc graphs to name a few) have been characterized in many ways, but we show that analogous characterizations do not hold if k >?2. We characterize the cocomparability interval 3-graphs via one forbidden subgraph and hence interval 3-orders via one forbidden suborder.     

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.     

Angle orders

A finite poset is an angle order if its points can be mapped into angular regions in the plane so thatx precedesy in the poset precisely when the region forx is properly included in the region fory. We show that all posets of dimension four or less are angle orders, all interval orders are angle orders, and that some angle orders must have an angular region less than 180° (or more than 180°). The latter result is used to prove that there are posets that are not angle orders.The smallest verified poset that is not an angle order has 198 points. We suspect that the minimum is around 30 points. Other open problems are noted, including whether there are dimension-5 posets that are not angle orders.Research supported in part by the National Science Foundation, grant number DMS-8401281.     

Numerical Representation of Semiorders

We introduce a codomain to represent semiorders, total preorders and interval orders by means of a single map. We characterize the semiorders that are representable in the extended real line.     

Tube Representations of Ordered Sets

We define the (n,i,f)-tube orders, which include interval orders, trapezoid orders, triangle orders, weak orders, order dimension n, and interval-order-dimension n as special cases. We investigate some basic properties of (n,i,f)-tube orders, and begin classifying them by containment. Mathematics Subject Classifications (2000) 06A06, 05C62.     

NP-hardness results for the aggregation of linear orders into median orders

Given a collection Π of individual preferences defined on a same finite set of candidates, we consider the problem of aggregating them into a collective preference minimizing the number of disagreements with respect to Π and verifying some structural properties. We study the complexity of this problem when the individual preferences belong to any set containing linear orders and when the collective preference must verify different properties, for instance transitivity. We show that the considered aggregation problems are NP-hard for different types of collective preferences (including linear orders, acyclic relations, complete preorders, interval orders, semiorders, quasi-orders or weak orders), if the number of individual preferences is sufficiently large.     

Finite Intervals in the Lattice of Topologies

We discuss the question whether every finite interval in the lattice of all topologies on some set is isomorphic to an interval in the lattice of all topologies on a finite set – or, equivalently, whether the finite intervals in lattices of topologies are, up to isomorphism, exactly the duals of finite intervals in lattices of quasiorders. The answer to this question is in the affirmative at least for finite atomistic lattices. Applying recent results about intervals in lattices of quasiorders, we see that, for example, the five-element modular but non-distributive lattice cannot be an interval in the lattice of topologies. We show that a finite lattice whose greatest element is the join of two atoms is an interval of T ₀-topologies iff it is the four-element Boolean lattice or the five-element non-modular lattice. But only the first of these two selfdual lattices is an interval of orders because order intervals are known to be dually locally distributive.     

On quadratic integral equation of fractional orders

We present an existence theorem for a nonlinear quadratic integral equations of fractional orders, arising in the queuing theory and biology, in the Banach space of real functions defined and continuous on a bounded and closed interval. The concept of measure of noncompactness and a fixed point theorem due to Darbo are the main tool in carrying out our proof.