Search

An alternative to Hanlon's buried-subgraph characterization of interval graphs that have unique (up to duality) agreeing interval orders is proveded. The alternative is based on a relation L between ordered pairs of points that are adjacent in the interval graph. The interpretation of abLxy is that if the interval for a precedes (follows) the interval for b in a representation of the interval graph, then the interval for x must precede (follow) the interval for y.

In 1941, Dushnik and Miller introduced the concept of the dimension of a poset (X, P) as the minimum number of linear extensions of P whose intersection is exactly P. Although Dilworth has given a formula for the dimension of distributive lattices, the general problem of determining the dimension of a poset is quite difficult. An equally difficult problem is to classify those posets which are dimension irreducible, i.e., those posets for which the removal of any point lowers the dimension. In this paper, we construct for each n>=3, k>=0, a poset, called a crown and denoted S^k"n, for which the dimension is given by the formula [email protected]?(n+k)(k+2). Furthermore, for each t>=3, we show that there are infinitely many crowns which are irreducible and have dimension t. We then demonstrate a method of combining a collection of irreducible crowns to form an irreducible poset whose dimension is the sum of the crowns in the collection. Finally, we construct some infinite crowns possessing combinatorial properties similar to finite crowns.

Let sk(n) be the largest integer such that every n-point interval order with no antichain of more than k points includes an sk(n)-point semiorder. When k = 1, s1(n) = n since all interval orders with no two-point antichains are chains. Given (c1,...,c5) = (1, 2, 3, 4), it is shown that s2(n) = cn for n ⩽ 4, s3(n) = cn for n ⩽ 5, and for all positive n, s2 (n+4) =s2(n)+3, s3(n+5) = s3(n)+3. Hence s2 has a repeating pattern of length 4 [1, 2, 3, 3; 4, 5, 6, 6; 7, 8, 9, 9;...], and s3 has a repeating pattern of length 5 [1, 2, 3, 3, 4; 4, 5, 6, 6, 7; 7, 8, 9, 9, 10;...].Let s(n) be the largest integer such that every n-point interval order includes an s(n)-point semiorder. It was proved previously that s(n-1) = s(n) = 12n +1 for even n from 4 to 14, and that s(17) = 9. We prove here that s(15) = s(16) = 9, so that s begins 1, 2, 3, 3, 4, 4,..., 8, 8, 9, 9, 9. Since s(n)/n→0, s cannot have a repeating pattern.

The recognition complexity of interval orders is shown to be Ω ( n log 2 n ), and an optimal algorithm is given for the identification of semiorders.

Following both the Debreu-Rader and the Arrow-Hahn approaches, we establish conditions under which an interval order > on a topological space X can be represented by a pair of real-valued functions u, v on X, in the sense that x > y if and only if u(x)>v(y). The semicontinuity of the functions u and v is also investigated.

The dimension of a partially ordered set (X, P) is the smallest positive integer t for which there exists a function ƒ which assigns to each x∈X a sequence {ƒ(x)(i): 1⩽i⩽t} of real numbers so that xles;y in P if and only if ƒ(x)(i)⩽ƒ(y)(i) for each i=1,2,…, t. The interval dimension of (X, P) is the smallest integer t for which there exists a function F which assigns to each x∈X a sequence {F(x)(i): 1⩽i⩽t} of closed intervals of the real line R so that x < y in P if and only if a < b in R for every a∈F(x)(i), b∈F(y)(i), and i = 1,2…,t. For t⩾2, a partially ordered set (poset) is said to be t-irreducible (resp. t-interval irreducible) if it has dimension t (resp. interval dimension t), and every proper subposet has dimension (resp. interval dimension) less than t. The only 2-irreducible poset is a two element anti-chain, and the only 2-interval irreducible poset is the free sum of two chains each having two points. In sharp contrast, the collection R of all 3-irreducible posets consists of 9 infinite families and 18 odd examples, and the collection RI of all 3-interval irreducible posets is sufficiently complex to have avoided complete determination as of this date. Trotter and Moore determined R from Gallai's forbidden subgraph characterization of comparability graphs. David Kelly independently determined R by a lattice theoretic argument combined with the characterization of planar lattices Kelly and Ivan Rival had previously obtained. In this paper, we introduce a new operation called a stack which we will apply to posets of height one. In some ways the stack operation is an inverse of the split operation on posets previously defined by Kimble. These operations behave predictably with respect to dimension and interval dimension. In particular, the stack of a poset of height one plays a role in interval dimension theory which is analogous to the role played by the completion by cuts in dimension theory. As a consequence, we can exploit the similarities to Kelly's approach to the determination of R to produce a relatively compact argument to determine the collection R(I, 1) of all 3-interval irreducible posets of height one. This characterization problem has immediate combinatorial connections with a wide range of well-known forbidden subgraph problems including interval graphs, rectangle graphs, and circular arc graphs.

Let > be a preference relation on a countable set X . We prove that if > is acyclic (that is, has irreflexive transitive closure), then there exists a mapping u of X into R such that x > y entails u ( x )> u ( y ). We also give a simple proof of a representation theorem of Fishburn when > is an interval order.

An interval order is a binary relation ≺ on a set X that is irreflexive and satisfies the condition: if x ≺ y and z ≺ w then x ≺ w or z ≺ y . An interval order is a special kind of strict partial order (transitive, irreflexive) and a generalization of the semiorder concept. If X is countable then there are real-valued functions u and p on X such that p is positive and [ x ≺ y if and only if u ( x ) + p ( x ) u ( y )], if and only if ≺ is an interval order.

It is a scientific platitude that there can be neither precise control nor prediction of phenomena without measurement. Disciplines are diverse as cosmology and social psychology provide evidence that it is nearly useless to have an exactly formulated quantitative theory if empirically feasible methods of measurement cannot be developed for a substantial portion of the quantitative concepts of the theory. Given a physical concept like that of mass or a psychological concept like that of habit strength, the point of a theory of measurement is to lay bare the structure of a collection of empirical relations which may be used to measure the characteristic of empirical phenomena corresponding to the concept. Why a collection of relations? From an abstract standpoint a set of empirical data consists of a collection of relations between specified objects. For example, data on the relative weights of a set of physical objects are easily represented by an ordering relation on the set; additional data, and a fortiori an additional relation, are needed to yield a satisfactory quantitative measurement of the masses of the objects.The major source of difficulty in providing an adequate theory of measurement is to construct relations which have an exact and reasonable numerical interpretation and yet also have a technically practical empirical interpretation. The classical analyses of the measurement of mass, for instance, have the embarrassing consequence that the basic set of objects measured must be infinite. Here the relations postulated have acceptable numerical interpretations, but are utterly unsuitable empirically. Conversely, as we shall see in the last section of this paper, the structure of relations which have a sound empirical meaning often cannot be succinctly characterized so as to guarantee a desired numerical interpretation.

We characterize those interval graphs G with the property that, for every vertex v , there exists an interval representation of G in which the interval representing v is the left-most (or right-most) interval in the representation.

In this paper we consider posets in which each order interval [a,b] is a continuous poset or continuous domain. After developing some basic theory for such posets, we derive our major result: if X is a core compact space and L is a poset equipped with the Scott topology (assumed to satisfy a mild extra condition) for which each interval is a continuous sup-semilattice, then the function space of continuous locally bounded functions from X into L has intervals that are continuous sup-semilattices. This substantially generalizes known results for continuous domains.

Dushnik and Miller defined the dimensions of a partially ordered set X,denoted dim X, as the smallest positive integer t for which there exist t linear extensions of X whose intersection is the partial ordering on X. Hiraguchi proved that if n ≥2 and |X| ≤2n+1, then dim X ≤ n. Bogart, Trotter and Kimble have given a forbidden subposet characterization of Hiraguchi's inequality by determining for each n ≥ 2, the minimum collection of posets ϱn such that if |X| ⩽2n+1, the dim X < n unless X contains one of the posets from ϱn. Although |ϱ3|=24, for each n ≥ 4, ϱn contains only the crown S0n — the poset consisting of all 1 element and n − 1 element subsets of an n element set ordered by inclusion. In this paper, we consider a variant of dimension, called interval dimension, and prove a forbidden subposet characterization of Hiraguchi's inequality for interval dimension: If n ≥2 and |X 2n+1, the interval dimension of X is less than n unless X contains S0n.

Given a partially ordered set P = (X, P), a function F which assigns to each x ∈ X a set F(x) so that x < y in P if and only if F(x) ⊂- F(y) is called an inclusion representation. Every poset has such a representation, so it is natural to consider restrictions on the nature of the images of the function F. In this paper, we consider inclusion representations assigning to each x ∈ X a sphere in Rd, d-dimensional Euclidean space. Posets which have such representations are called sphere orders. When d=1, a sphere is just an interval from R, and the class of finite posets which have an inclusion representation using intervals from R consists of those posets which have dimension at most two. But when d ⩾ 2, some posets of arbitrarily large dimension have inclusion representations using spheres in Rd. However, using a theorem of Alon and Scheinerman, we know that not all posets of dimension d + 2 have inclusion representations using spheres in Rd. In 1984, Fishburn and Trotter asked whether every finite 3-dimensional poset has an inclusion representation using spheres (circles) in R2. In 1989, Brightwell and Winkler asked whether every finite poset is a sphere order and suggested that the answer was negative. In this paper, we settle both questions by showing that there exists a finite 3-dimensional poset which is not a sphere order. The argument requires a new generalization of the Product Ramsey Theorem which we hope will be of independent interest.

This is the third paper in the series. Here we define a few combinatorial orders on Young tableaux. The first order is obtained from the induced Duflo order by the extension with the help of Vogan T α , β procedure. We call it the Duflo–Vogan order. The second order is obtained from the generalization of Spaltenstein's construction by consideration of an orbital variety as a double chain of nilpotent orbits. We call it the chain order. Again, we use Vogan's T α , β procedure, however, this time to restrict the chain order. We call it the Vogan-chain order. The order on Young tableaux defined by the inclusion of orbital variety closures is called the geometric order and the order on Young tableaux defined by inverse inclusion of primitive ideals is called the algebraic order. We get the following relations between the orders: the Duflo–Vogan order is an extension of the induced Duflo order; the algebraic order is an extension of the Duflo–Vogan order; the geometric order is an extension of the algebraic order; the Vogan-chain order is an extension of the geometric order; and, finally, the chain order is an extension of the Vogan-chain order. The computations show that the Duflo–Vogan and the Vogan-chain orders coincide on sl n for n ⩽ 9 and in n = 10 there is one case (up to T α , β procedure and transposition) where the chain-Vogan order is a proper extension of the Duflo–Vogan order. In this only case the algebraic order coincides with the Vogan-chain order. These computations permit us to conjecture that in sl n the algebraic order coincides with the geometric order. As well we conjecture that the combinatorics of both the inclusions on primitive ideals and on orbital variety closures is defined by the Vogan-chain order on Young tableaux.

A poset is {\it $(\3+\1)$-free} if it contains no induced subposet isomorphic to the disjoint union of a 3-element chain and a 1-element chain. These posets are of interest because of their connection with interval orders and their appearance in the $(\3+\1)$-free Conjecture of Stanley and Stembridge. The dimension 2 posets $P$ are exactly the ones which have an associated permutation $\pi$ where $i\prec j$ in $P$ if and only if $i, Comment: 17 pages

An interval bigraph is an undirected bipartite graph whose edge set is the intersection of the edge sets of an interval graph and the edge set of a complete bipartite graph on the same vertex set. A bipartite interval representation of an interval bigraph is given by a bipartitioned set of intervals for its vertices, such that vertices are adjacent if and only if the corresponding intervals intersect and belong to opposite sides of the bipartition. Interval digraphs are directed graphs defined by a closely related concept. Each vertex of an interval digraph is represented by two intervals on the real line, a source interval and a target interval. The directed arc ( u , v ) exists in the interval digraph if the source interval of u meets the target interval of v . We give a dynamic programming algorithm recognizing interval bigraphs (interval digraphs) in polynomial time. This algorithm recursively constructs a bipartite interval representation of a graph from bipartite interval representations of proper subgraphs. Moreover, we list some forbidden substructures of interval bigraphs.

Consider a graded poset P with maximal and minimal elements. If everey interval of rank three in P is a product of chains, and for everey interval [x, y] of rank at least four, the open interval (x, y) is connected, we show that the entire poset is a product of chains. This proves a conjecture of Stanley concerning the natural local action of the symmetric group on maximal chains in a graded poset. On a product of chains, the natural action is thepermutation action on the multiset corresponding to the chains. The result implies that if every open interval is connected (which holds if the poset is Cohen-Macaulay, for example), the only possible such natural action is this multiset action.

The interval count problem determines the smallest number of interval lengths needed in order to represent an interval model of a given interval graph or interval order. Despite the large number of studies about interval graphs and interval orders, surprisingly only a few results on the interval count problem are known. In this work, we provide a short survey about the interval count and related problems. a graph and the number of its maximal cliques.

The class of quasi-interval orders contains properly two rich families of precedence graphs: interval orders and a subclass of series–parallel orders. In this paper, we consider the problem of scheduling unitary task systems with zero–one communication delays in order to minimize the total elapsed time for the execution of all the tasks. This problem is known to be NP-complete on an unlimited number of processors even for interval orders. When the precedence constraints are given by a quasi-interval order G and the communication delays are locally identical (which includes the UET-UCT case), we show that an optimal static scheduling can be determined in O(nlogn+e) time where n denotes the number of tasks and e denotes the number of the precedence constraints in the transitive closure of G. Some extensions are discussed for nonquasi-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.

This paper considers the problem of listing all linear extensions of a partial order so that successive extensions differ by the transposition of a single pair of elements. A necessary condition is given for the case when the partial order is a forest. A necessary and sufficient condition is given for the case where the partial order consists of disjoint chains. Some open problems are mentioned.

A symmetric, antireflexive relation S is a comparability graph if one can assign a transitive orientation to the edges: we obtain a partial order. We say that S is a comparability graph with constraint C , a subrelation of S , if S has a transitive orientation including C . A characterization is given in terms of antisymmetry of a super-constraint build from C . We study a special case where this super-constraint is a multi-weak order (i.e., a family of weak orders), and apply the results to generalize, in the partial case, the notions of semi-order and of interval order.

In this note we prove that any finite interval order P can be represented in the plane by using translations of line segments, each one having a single direction of motion. We state that |Succ(P)| different directions are sufficient.

Containment and overlap representations of digraphs are studied, with the following results. The interval containment digraphs are the digraphs of Ferrers dimension 2, and the circular-arc containment digraphs are the complements of circular-arc intersection digraphs. A poset is an interval containment poset if and only if its comparability digraph is an interval containment digraph, and a graph is an interval graph if and only if the corresponding symmetric digraph with loops is an interval digraph. In an appropriate model of overlap representation using intervals, the unit right-overlap interval digraphs are precisely the unit interval digraphs, and the adjacency matrices of right-overlap interval digraphs have a simple structural characterization bounding their Ferrers dimension by 3.

We show how the theory of “probabilistic consistency” developped in the framework of pair comparison methods with forced choice con be extended to arbitrary valued preference relations. Especially we generalize classical “stochastic transitivity” conditions securing the “linearity” of valued relations and we study the implications between such conditions.

Let A be a finite set of feasible actions and let γ i (a) be the evaluation of an action a in A on the ith criterion. An outranking S A defined on A is by definition: aS A b for a and b in A if it is realistic to accept a as preferred to b for the decision maker, as far as we are able to catch his preferences among the criteria and as far as we can take into account the often poor quality of the data (the evaluation γ i (a)). To do this, we consider the preference of the decision maker on each criterion as a semi-order instead of weak-order as it is usually done in multi-criteria decision making. Then, we show two kinds of models which use this notion of semiorder to build outranking relations. The first one deals with weights on each criterion and concord tests in the way of the method ELECTRE of the Metra Group. The second one deals with a method which supposes the existence of a value function, on which one tries to reduce uncertainty on trade-off ratio approximations.

This chapter explains partial orders and lattices. Lattices are defined in terms of two operations analogous to set intersection and union. These induce a partial order analogous to subset ordering. Lattices have application both to explicit definition and to the development of Boolean algebra. Whenever there is a noncyclic relationship on the elements of a set, this relationship provides a natural partial order for the set. For example, any cycle-free directed graph displays explicitly a partial order on the vertices of the graph. In particular, the flowchart for a loop-free program displays a partial order on the computation steps, the order in which the computations are performed. Small loops can even be accommodated into the order if each entire loop is considered as a single entity. The useful partial orders are related to the linear order of the integers or to an alphabetical order.

In this chapter we define partial interval order and partial semiorder structures. In order to ensure terminology coherence we require the following properties: (i) partial structures must coincide with corresponding total structures when R = o; (ii) partial structures must coincide with a quasi order (partial preorder) structure when property I c I is satisfied and with a partial order structure when I = {(a,a), ∀ a ∈ A}, (iii) partial structures must be compatible with a numerical representation.

A complete two-valued preference structure in a finite set A is a mapping from A×A to [−1, +1] such that, V a, b ∈ A: $${\rm{\mu }}\left( {{\rm{a,b}}} \right) + {\rm{\mu }}\left( {{\rm{b,a}}} \right) = 0.$$

Preference modelling often uses concents such as preorders, semiorders and interval orders and, in most cases, it is assumed that the relations are comolete (no incomparability). However, incomparabilities naturally appear in many decision problems, as for example, in multicriteria problems. That is the reason why the study of partial relations becomes more and more important. In this paper, we Propose a definition of partial interval order which extends the concent of interval order, which is compatible with a numerical representation and which is defined by properties very easy to verify.

It appears that microcomputers will play a more and more important part in the use of multiple criteria decision aid methods. It is thus interesting to evaluate the impact of the implementation design on response time. In this respect, one of the most valuable means is the concept which has been called ‘time complexity’ of algorithms. This time complexity is rather dependent on the data structures used to represent and to manipulate the objects involved in the algorithms.

In this paper we survey complexity results yielded by the calculation of untractable invariants of ordered sets dealing with the computation of linear extensions. The main invariants we consider here are the dimension, the jump number, and the number of linear extensions.

This paper surveys results concerning packing/covering parameters and representation parameters of graphs and posets. We start from the poset param¬eters known as width and dimension. We consider generalizations, related ques¬tions, and analogous parameters for graphs and/or directed graphs.

Interval orders and semiorders ore models of preference structures involving a discrimination threshold. Recently two kinds of generalizations were described: one leads to the corresponding partial structures, the other covers the case of multiple levels of preference. Here the two extensions are combined. Numerical representations of the ensuing structures are derived from a general result on directed weighted multiple graphs.

Publisher Summary This chapter describes the interval contractions for the solution of integral equations. It discusses the uses of the interval methods. The interval approach is used to avoid the monotonicity condition but with a special interval extension of T that preserves the contraction property. This approach can easily be adapted to intervals with other endpoints than piecewise constant functions to obtain higher order methods. The interval approach of Moore has the drawback that the interval extension of T does not necessarily inherit the contraction property of T and therefore, the iteration will not converge to the fixed point y *. The chapter describes two purposes of the interval methods: (1) the interval approach is used to avoid the monotonicity condition but with a special interval extension of T preserves the contraction property; (2) this approach can easily be adapted to intervals with other endpoints than piecewise constant functions to obtain higher order methods.

This paper is concerned with preference models including four relations: strict preference (P), weak preference (Q), indifference (I) and incomparability (J). The purpose is to establish conditions allowing to represent these four relations by numerical functions and thresholds, in order to generalize previous results concerning complete or partial semiorders and interval orders, pseudo-orders and {P, Q, I} — preference structures.

Finite interval orders are finite sets ordered by a relation P whose points can be mapped into closed intervals such that xPy precisely when x 's interval is wholly to the right of y 's interval. It is conjectured that the smallest interval order whose interval representation must use at least k different interval lengths has 3 k –2 points. This conjecture, which remains open, motivates work on several aspects of interval orders that are explored in the paper. The least number of points to force k lengths is shown to lie between 2 k and 3 k –2. Sets of inequalities that govern lengths and end-point placements are developed, and the latter are shown to lead to other interesting results and conjectures.

Let Φ={P 1,...,P m } be a family of sets. A partial order P(Φ

Bipartitional relations were introduced by Foata and Zeilberger in their characterization of relations which give rise to equidistribution of the associated inversion statistic and major index. We consider the natural partial order on bipartitional relations given by inclusion. We show that, with respect to this partial order, the bipartitional relations on a set of size n form a graded lattice of rank 3 n - 2 . Moreover, we prove that the order complex of this lattice is homotopy equivalent to a sphere of dimension n - 2 . Each proper interval in this lattice has either a contractible order complex, or is isomorphic to the direct product of Boolean lattices and smaller lattices of bipartitional relations. As a consequence, we obtain that the Mobius function of every interval is 0, 1, or -1. The main tool in the proofs is discrete Morse theory as developed by Forman, and an application of this theory to order complexes of graded posets, designed by Babson and Hersh, in the extended form of Hersh and Welker.

We present statistic-preserving bijections between four classes of combinatorial objects. Two of them, the class of unlabeled $(\textrm{2+2})$-free posets and a certain class of chord diagrams (or involutions), already appeared in the literature, but were apparently not known to be equinumerous. The third one is a new class of pattern avoiding permutations, and the fourth one consists of certain integer sequences called $\textit{ascent sequences}$. We also determine the generating function of these classes of objects, thus recovering a non-D-finite series obtained by Zagier for chord diagrams. Finally, we characterize the ascent sequences that correspond to permutations avoiding the barred pattern $3\bar{1}52\bar{4}$, and enumerate those permutations, thus settling a conjecture of Pudwell., Nous présentons des bijections, transportant de nombreuses statistiques, entre quatre classes d'objets. Deux d'entre elles, la classe des EPO (ensembles partiellement ordonnés) sans motif $(\textrm{2+2})$ et une certaine classe d'involutions, sont déjà apparues dans la littérature. La troisième est une classe de permutations à motifs exclus, et la quatrième une classe de suites que nous appelons $\textit{suites à montées}$. Nous déterminons ensuite la série génératrice de ces classes, retrouvant ainsi un résultat prouvé par Zagier pour les involutions sus-mentionnées. La série obtenue n'est pas D-finie. Apparemment, le fait qu'elle compte aussi les EPO sans motif $(\textrm{2+2})$ est nouveau. Finalement, nous caractérisons les suites à montées qui correspondent aux permutations évitant le motif barré $3\bar{1}52\bar{4}$ et énumérons ces permutations, ce qui démontre une conjecture de Pudwell.

Cytoplasmic incompatibility (CI) relates to the manipulation by the parasite Wolbachia of its host reproduction. Despite its widespread occurrence, the molecular basis of CI remains unclear and theoretical models have been proposed to understand the phenomenon. We consider in this paper the quantitative Lock-Key model which currently represents a good hypothesis that is consistent with the data available. CI is in this case modelled as the problem of covering the edges of a bipartite graph with the minimum number of chain subgraphs. This problem is already known to be NP-hard, and we provide an exponential algorithm with a non trivial complexity. It is frequent that depending on the dataset, there may be many optimal solutions which can be biologically quite different among them. To rely on a single optimal solution may therefore be problematic. To this purpose, we address the problem of enumerating (listing) all minimal chain subgraph covers of a bipartite graph and show that it can be solved in quasi-polynomial time. Interestingly, in order to solve the above problems, we considered also the problem of enumerating all the maximal chain subgraphs of a bipartite graph and improved on the current results in the literature for the latter. Finally, to demonstrate the usefulness of our methods we show an application on a real dataset.

We characterize the representability of an interval order on a topological space through a pair of continuous real-valued functions which in addition represent two total preorders associated to the given interval order. Such a continuous representation is obtained by using the notion of a decreasing scale.

The rough approximations are considered in the context of multi-criteria classification problem where evaluations of objects on particular criteria and their assignments to decision classes are imprecise and given in the form of intervals of possible values. Within Dominance-based Rough Set Approach (DRSA), the lower and upper approximations reflect the inconsistencies with respect to dominance principle. In the considered case, also the interval assignments have to be taken into account. This requires a new formulation of the dominance principle. A possible solution to the problem consists in introducing the second-order rough approximations. The methodology based on these approximations preserves well-known properties of rough approximations, such as rough inclusion, complementarity, identity of boundaries and monotonicity.

It follows from a theorem of Szpilrajn that any partial order (X