Search

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.

We introduce posets with interfaces (iposets) and generalise their standard serial composition to a new gluing composition. In the partial order semantics of concurrency, interfaces and gluing allow modelling events that extend in time and across components. Alternatively, taking a decompositional view, interfaces allow cutting through events, while serial composition may only cut through edges of a poset. We show that iposets under gluing composition form a category, which generalises the monoid of posets under serial composition up to isomorphism. They form a 2-category when a subsumption order and a lax tensor in the form of a non-commutative parallel composition are added, which generalises the interchange monoids used for modelling series-parallel posets. We also study the gluing-parallel hierarchy of iposets, which generalises the standard series-parallel one. The class of gluing-parallel iposets contains that of series-parallel posets and the class of interval orders, which are well studied in concurrency theory, too. We also show that it is strictly contained in the class of all iposets by identifying several forbidden substructures. [ABSTRACT FROM AUTHOR]

Abstract: The jump number problem is to find a linear extension of a given poset that minimizes the number of incomparable adjacent elements. The problem is NP-hard even in the class of interval orders and so three different 3/2-approximation algorithms for this case have been proposed respectively by Felsner, Sysło, and Mitas. We build upon the approach of Mitas, where the problem is reduced to packing vertex-disjoint edges and odd cycles in a certain graph. We prove that the requirement of independence between edges and cycles may be abandoned. In effect, the jump number problem is reduced to the set cover problem, and the 4/3-approximation algorithm of Duh and Fürer for the 3-set cover problem is used to show that the approximation ratio of the jump number problem on interval orders is tighter than 89/60. [Copyright &y& Elsevier]

Generalizations of partial meet contraction are introduced that start out from the observation that only some of the logically closed subsets of the original belief set are at all viable as contraction outcomes. Belief contraction should proceed by selection among these viable options. Several contraction operators that are based on such selection mechanisms are introduced and then axiomatically characterized. These constructions are more general than the belief base approach. It is shown that partial meet contraction is exactly characterized by adding to one of these constructions the condition that all logically closed subsets of the belief set can be obtained as the outcome of a single (multiple) contraction. Examples are provided showing the counter-intuitive consequences of that condition, thus confirming the credibility of the proposed generalization of the AGM framework. [ABSTRACT FROM AUTHOR]

Abstract: The jump number problem for posets is to find a linear extension in which the number of incomparable adjacent pairs is minimized. In this paper the class of interval orders is considered. Three 3/2-approximation algorithms for this problem have been known for some time. By a previous work of Mitas, the problem may be reformulated as a subgraph packing task. We prove that the problem reduces also to a set cover task, and we establish an improved bound of 1.484 to the approximation ratio of the jump number on interval orders. [Copyright &y& Elsevier]

We prove that if a finite ( 3 + 1)-free ordered set of height two has the fixed point property, then it is dismantlable by irreducibles. We provide an example of a finite ( 3 + 1)-free ordered set of height three with the fixed point property and no irreducible elements. We characterize the minimal automorphic ordered sets which are respectively ( 3 + 1)-free, ( 2 + 2)-free and N-free. [ABSTRACT FROM AUTHOR]

Copyright of Mathématiques & Sciences Humaines is the property of Editions du CNRS and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

This paper studies an extension of biorders that has a 'frontier' between the relation and the absence of relation. This extension is motivated by a conjoint measurement problem consisting in the additive representation of ordered coverings defined on product sets of two components. We also investigate interval orders and semiorders with frontier. [ABSTRACT FROM AUTHOR]

Abstract: Let be a poset in which each point is incomparable to at most others. Tanenbaum, Trenk, and Fishburn asked in a 2001 paper if the linear discrepancy of such a poset is bounded above by . This paper answers their question in the affirmative for two classes of posets. The first class is the interval orders, which are shown to have linear discrepancy at most , with equality precisely for interval orders containing an antichain of size . The stronger bound is tight even for interval orders of width 2. The second class of posets considered is the disconnected posets, which have linear discrepancy at most . This paper also contains lemmas on the role of critical pairs in linear discrepancy as well as a theorem establishing that every poset contains a point whose removal decreases the linear discrepancy by at most 1. [Copyright &y& Elsevier]

We introduce a new approach that deals, jointly and in a unified manner, with the topics of numerical (continuous) representability of total preorders and interval orders. This setting is based on the consideration of increasing scales and the systematic use of a particular kind of codomain, that has a key lattice theoretical structure of a completely distributive lattice and allows us to use a single function (taking values in that codomain) in order to represent both kinds of binary relations. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we study the binary relations on a nonempty -set which are h-independent and h-positive (cf. the introduction below). They are called homothetic positive orders. Denote by the set of intervals of having the form with or with . It is a -set endowed with a binary relation extending the usual one on (identified with a subset of via the map ). We first prove that there exists a unique map such that (for all and all ) we have and . Then we give a characterization of the homothetic positive orders on such that there exist two morphisms of -sets satisfying . They are called generalized homothetic biorders. Moreover, if we impose some natural conditions on the sets and , the representation is “uniquely” determined by . For a generalized homothetic biorder on , the binary relation on defined by is a generalized homothetic weak order; i.e. there exists a morphism of -sets such that (for all ) we have . As we did in [B. Lemaire, M. Le Menestrel, Homothetic interval orders, Discrete Math. 306 (2006) 1669–1683] for homothetic interval orders, we also write “the” representation of in terms of and a twisting factor. [Copyright &y& Elsevier]

Abstract: We prove that a prime interval order, not necessarily finite, has no prime upper cover if and only if it has width two. On the other hand, we prove that every finite prime -free order has at least one prime upper cover. [Copyright &y& Elsevier]

Abstract: Maximal elements of a binary relation on compact subsets of a metric space define a choice function. An infinite extension of transitivity is necessary and sufficient for such a choice function to be nonempty-valued and path independent (or satisfy the outcast axiom). An infinite extension of acyclicity is necessary and sufficient for the choice function to have nonempty values provided the underlying relation is an interval order. [Copyright &y& Elsevier]

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. [ABSTRACT FROM AUTHOR]

A perfect Guttman scale is rarely found in real data. Pairwise dominance relations between items to be scaled, however, often meet the conditions for less simple orders, such as strict partial orders, interval orders, and semiorders. Examples are thus provided for an extension of the Guttman scale to less simple orders in the framework of ordinal theory, or more specifically, the theory of representations with thresholds. The study is methodologically based on ordering theory. Three illustrative constructions of less simple orders demonstrate that they much more strongly account for real data than do Guttman scales, and that some uniqueness in scale values and thresholds is found in semiorders and interval orders. [ABSTRACT FROM AUTHOR]

Abstract: Consider a horizontal line in the plane and let be a collection of n circles, possibly of different sizes all tangent to the line on the same side. We define the tangent circle graph associated to as the intersection graph of the circles. We also define an irreflexive and asymmetric binary relation P on A; the pair representing two circles of is in P iff the circle associated to a lies to the right of the circle associated to b and does not intersect it. This defines a new nontransitive preference structure that generalizes the semi-order structure. We study its properties and relationships with other well-known order structures, provide a numerical representation and establish a sufficient condition implying that P is transitive. The tangent circle preference structure offers a geometric interpretation of a model of preference relations defined by means of a numerical representation with multiplicative threshold; this representation has appeared in several recently published papers. [Copyright &y& Elsevier]

On-line chain partitioning problem of on-line posets has been open for the past 20 years. The best known on-line algorithm uses 5w-1 / 4 chains to cover poset of width w. Felsner (Theor. Cornput. Sci., 175(2):283-292, 1997) introduced a variant of this problem considering only up-growing posets, i.e. on-line posets in which each new point is maximal at the moment of its arrival. He presented an algorithm using (w+1 / 2) chain's for width w posets and proved that his solution is optimal. In this paper, we study on-line chain partitioning of up-growing interval orders. We prove lower bound and upper bound to be 2w - 1 for width w posets. [ABSTRACT FROM AUTHOR]

Abstract: We give a characterization of the non-empty binary relations on a -set A such that there exist two morphisms of -sets verifying and . They are called homothetic interval orders. If is a homothetic interval order, we also give a representation of in terms of one morphism of -sets and a map such that . The pairs and are “uniquely” determined by , which allows us to recover one from each other. We prove that is a semiorder (resp. a weak order) if and only if is a constant map (resp. ). If moreover A is endowed with a structure of commutative semigroup, we give a characterization of the homothetic interval orders represented by a pair so that u is a morphism of semigroups. [Copyright &y& Elsevier]

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. [ABSTRACT FROM AUTHOR]

In the framework of interval decision making, the available information is vague and numerically imprecise, and decision situations are modelled by imprecise probabilities and utilities that are simply represented by suitable intervals and comparisons. Alternatives are therefore evaluated in terms of interval expected utilities, which are then used for expressing crisp preferences among these alternatives. In this work, we construct a valued preference relation expressing the degree to which an alternative is considered as better than another alternative, based on the overlap between these interval expected utilities. In particular, we study a chain of interval order relations associated with the proposed valued preference relation and introduce the notion of a-admissibility in terms of non-dominated alternatives induced by such relations. Furthermore, we consider a possible ranking of the admissible alternatives w.r.t. the corresponding degrees of preference/dominance. In addition, the decision maker is provided with the possibility to state a threshold, expressing his/her own ideas, understanding, views etc., based upon which an alternative can be regarded as better than another one. Thus the admissible alternatives can be defined as non-dominated alternatives w.r.t. the stated degree of preference. [ABSTRACT FROM AUTHOR]

Abstract: Binary relations representable by utility functions with multiplicative error are considered. It is proved that if the error is a power of utility then the underlying binary relation is either an interval order, or a semiorder. Moreover, semiorders can be characterized among interval orders by the magnitude of the power of utility that is used in the form of error function. [Copyright &y& Elsevier]

This paper enumerates according to height the classes of unlabeled N-free posets, interval orders, and posets that are both N-free and interval orders. The last two classes are enumerated according to height in terms of generating functions. We apply an algorithmic method for height counting of connected N-free posets. Numerical results for n-element posets of height k, 1⩽k⩽n⩽14, are included. [Copyright &y& Elsevier]

We consider the scheduling problem of minimizing the average weighted job completion time on a single machine under precedence constraints. We show that this problem with arbitrary job weights, the special case of the problem where all job weights are one, and several other special cases of the problem all have the same approximability threshold with respect to polynomial time approximation algorithms. Moreover, for the special case of interval order precedence constraints and for the special case of convex bipartite precedence constraints, we give a polynomial time approximation algorithm with worst case performance guarantee arbitrarily close to the golden ratio 1/2(1+√ of 5)≈1.61803. [Copyright &y& Elsevier]

Partial orders can be represented by subsets of a given set ordered by inclusion. Special kinds of such set representations are investigated because they facilitate the exploration of properties of knowledge spaces. A new type of order relation is defined which is closely related to interval orders. These orders and the interval orders are investigated with respect to their parsimonious set representations. The theorems are applied to knowledge space theory. [Copyright &y& Elsevier]

The class of interval orders is one of the most studied classes of preference structures without incomparability in the theory of classical preference modelling. In this paper, we propose a generalization of the classical definition of interval order and strict interval order. We focus our attention on two important classes of interval orders and strict interval orders which are, respectively, defined by means of a strong De Morgan triplet and a min–max De Morgan triplet. [Copyright &y& Elsevier]

It is well known that interval orders are particularly interesting in decision theory, since they are reflexive, complete and nontransitive binary relations which may be fully represented by means of two real-valued functions. In this paper, we discuss the existence of a pair of nonnegative, positively homogeneous and semicontinuous real-valued functionals representing an interval order on a real cone in a topological vector space. We recover as a particular case a result concerning the existence of a nonnegative, positively homogeneous and continuous utility functional for a complete preorder on a real cone in a topological vector space. [ABSTRACT FROM AUTHOR]

A poset ( X,≺) is a split interval order (a.k.a. unit bitolerance order, proper bitolerance order) if a real interval and a distinguished point in that interval can be assigned to each x∈ X so that x≺ y precisely when x's distinguished point precedes y's interval, and x's interval precedes y's distinguished point. For each | X|≤9, we count the split interval orders and identify all posets that are minimal forbidden posets for split interval orders. The paper is a companion to “Counting Split Semiorders” by Fishburn and Reeds (this issue). [ABSTRACT FROM AUTHOR]

Erhlich introduced the concept of generating combinatorial structures in constant time per generated item. Such algorithms are called “loopless” and have been described for many objects. Myers introduced the idea of a basic minimal interval order. This paper presents a loopless algorithm for generating basic minimal interval orders. [ABSTRACT FROM AUTHOR]

Multiple definitions have been put forward in the literature to measure the differences between two interval-valued fuzzy sets. However, in most cases, the outcome is just a real value, although an interval could be more appropriate in this environment. This is the starting point of this contribution. Thus, we revisit the axioms that a measure of the difference between two interval-valued fuzzy sets should satisfy, paying special attention to the condition of monotonicity in the sense that the closer the intervals are, the smaller the measure of difference between them is. Its formalisation leads to very different concepts: distances, divergences and dissimilarities. We have proven that distances and divergences lead to contradictory properties for this kind of sets. Therefore, we conclude that dissimilarities are the only appropriate measures to measure the difference between two interval-valued fuzzy sets when the outcome is an interval. [ABSTRACT FROM AUTHOR]

An interval order of length n has elements in correspondence with a collection of intervals in the linearly ordered set {1, 2, ..., n}. A basic interval order of length n has the property that removal of any element yields an order with length less than n. We construct and enumerate the set of basic length n interval orders. [ABSTRACT FROM AUTHOR]