Search

In general, representations of interval orders may use an arbitrary set of interval lengths. We can define subclasses of interval orders by restricting the allowable lengths of intervals. Motivated by a recent paper of Keller, Trenk, and Young, we study the dimension of posets in some of these subclasses. Among other results, we answer several of their questions, and we simplify the proof of one of their main results. [ABSTRACT FROM AUTHOR]

This paper examines the logic of conditional obligation, which originates from the works of Hansson, Lewis, and others. Some weakened forms of transitivity of the betterness relation are studied. These are quasi-transitivity, Suzumura consistency, acyclicity and the interval order condition. The first three do not change the logic. The axiomatic system is the same whether or not they are introduced. This holds true under a rule of interpretation in terms of maximality and strong maximality. The interval order condition gives rise to a new axiom. Depending on the rule of interpretation, this one changes. With the rule of maximality, one obtains the principle known as disjunctive rationality. With the rule of strong maximality, one obtains the Spohn axiom (also known as the principle of rational monotony, or Lewis' axiom CV). A completeness theorem further substantiates these observations. For interval order, this yields the finite model property and decidability of the calculus. [ABSTRACT FROM AUTHOR]

One way to verify the concurrent system is to sort the read and write events and control events in the concurrent system according to the sequence relationship, either in a partial order, or in a strict order. Due to the concurrency of the events and the timing of the written data events, there is an overlap between the events, which requires an interval order for analysis. The order structure of the entire interval order is represented by the start and end sequences, and the order is observed for all equivalent interval orders. Mazurkiewicz traces, Comtraces are hierarchical traces, but neither can describe the interval trace. The petri interval trace with data is the technique to solve the problem in this paper, DPN, the Petri net with data, to describe the interval trace of read and write data. The method used is a BE (Beginnings and Endings) sequence to represent a class of runs based on the interval sequence. The case multi-threaded system represents the interval of writing events, and according to the unfolding of Petri net, the analysis of the running trace involved by read and write data events is successfully analyzed. [ABSTRACT FROM AUTHOR]

We provide upper bounds on the L(p, q)-labeling number of graphs which have interval (or circular-arc) representations via simple greedy algorithms. We prove that there exists an L(p, q)-labeling with a span at most max{2(p+ q-1)Δ-4q+2, (2p-1)μ+(2q-1)Δ-2q+1} for interval k-graphs, max{p, q}Δ for interval graphs, 3max{p, q}Δ+p for circular-arc graphs, 2(p+q-1)Δ-2q +1 for permutation graphs and (2p-1)Δ+(2q -1)(μ-1) for cointerval graphs. In particular, these improve existing bounds on L(p, q)-labeling of interval graphs and L(2, 1)-labeling of permutation graphs. Furthermore, we provide upper bounds on the coloring of the squares of aforementioned classes. [ABSTRACT FROM AUTHOR]

We propose a novel mapping from a space of interval-valued functions defined on an arbitrary set to the family of closed subintervals of nonnegative extended real numbers, called the interval-valued Choquet-Sugeno-like operator. It is based on the notion of the Choquet-Sugeno-like operator and the interval-valued seminormed fuzzy operator introduced by Boczek et al. (2021) and generalizes many interval-valued operators known in the literature, such as n -ary interval-valued aggregation operators, interval-valued ordered weighting average operators, interval-valued seminormed fuzzy operators, and discrete interval-valued Choquet integral. We study its properties and show that it can be used to aggregate interval-valued data. [ABSTRACT FROM AUTHOR]

Rabinovitch showed in 1978 that the interval orders having a representation consisting of only closed unit intervals have order dimension at most 3 . This article shows that the same dimension bound applies to two other classes of posets: those having a representation consisting of unit intervals (but with a mixture of open and closed intervals allowed) and those having a representation consisting of closed intervals with lengths in 0 , 1 . [ABSTRACT FROM AUTHOR]

We consider a bilevel continuous knapsack problem where the leader controls the capacity of the knapsack and the follower chooses an optimal packing according to his own profits, which may differ from those of the leader. To this bilevel problem, we add uncertainty in a natural way, assuming that the leader does not have full knowledge about the follower's problem. More precisely, adopting the robust optimization approach and assuming that the follower's profits belong to a given uncertainty set, our aim is to compute a solution that optimizes the worst-case follower's reaction from the leader's perspective. By investigating the complexity of this problem with respect to different types of uncertainty sets, we make first steps towards better understanding the combination of bilevel optimization and robust combinatorial optimization. We show that the problem can be solved in polynomial time for both discrete and interval uncertainty, but that the same problem becomes NP-hard when each coefficient can independently assume only a finite number of values. In particular, this demonstrates that replacing uncertainty sets by their convex hulls may change the problem significantly, in contrast to the situation in classical single-level robust optimization. For general polytopal uncertainty, the problem again turns out to be NP-hard, and the same is true for ellipsoidal uncertainty even in the uncorrelated case. All presented hardness results already apply to the evaluation of the leader's objective function. [ABSTRACT FROM AUTHOR]

Abstract 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.

The inequality between genders is a problem virtually in all countries. A comparison among 28 nations of the European Union together with a data set corresponding to a population weighted average of all European Union nations is performed for the years 2006, 2010 and 2017, respectively. In order to compare the nations mutually, six indicators out of the United Nation's Sustainable Development Goal No 5 are scrutinized. Methods of Discrete Mathematics are applied as a tool to perform the comparisons methods. Partial order is an appropriate tool to inspect the role of all these six indicators to compare the nations. It is shown that an aggregation method is possible without the difficult task to introduce specific weights to the single indicators. Beyond this it is assumed that the data are associated with some uncertainty that should be taken into account. As a methodological result, we show that a special partial order is recommendable, the interval order; furthermore, a crude classification is found with Denmark at the top, Germany in the middle field and Czech Republic in a position which requires obviously some improvements. Further, applying an identical analytical methodology the development in gender equality over the period 2006 to 2017 for Denmark, Germany, and the Czech Republic was studied applying the population averaged data for the European Union as a reference point. [ABSTRACT FROM AUTHOR]

Given a partial order Q , its semiorder dimension is the smallest number of semiorders whose intersection is Q. When we look at the class of partial orders of fixed semiorder dimension k , no characterization is known, even in the case k = 2. In this paper, we give a characterization of the class of interval orders with semiorder dimension two. It follows from our results that partial orders that are interval orders with semiorder dimension two can be recognized efficiently. As our characterization makes use of a certain substructure, we also discuss the possibility of a forbidden suborder characterization. We give a partial answer to this question by listing all forbidden suborders for a special case. We further transfer our characterization result to the class of interval graphs that induce orders with semiorder dimension two. [ABSTRACT FROM AUTHOR]

Let λ ∈ 0 , 1 2 . We prove that, for ordered sets P of order dimension 2 and for interval orders, the ratio of the number of automorphisms to the number of endomorphisms is asymptotically bounded by 2 − | P | λ . The key to the proof is to establish this bound for certain types of lexicographic sums. [ABSTRACT FROM AUTHOR]

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

In this paper, we provide a characterization of the existence of a representation of an interval order on a topological space in the general case by means of a pair of continuous functions, when neither the functions nor the topological space are required to satisfy any particular assumptions. Such a characterization is based on a suitable continuity assumption of the binary relation, called weak continuity. In this way, we generalize all the previous results on the continuous representability of interval orders, and also of total preorders, as particular cases. [ABSTRACT FROM AUTHOR]

It was recently proved that the dualization in lattices given by implicational bases is impossible in output-polynomial time unless P = NP. In this paper, we show that this result holds even when the premises in the implicational base are of size at most two. Then we show using hypergraph dualization that the problem can be solved in output quasi-polynomial time whenever the implicational base has bounded independent-width, defined as the size of a maximum set of implications having independent conclusions. Lattices that share this property include distributive lattices coded by the ideals of an interval order, when both the independent-width and the size of the premises equal one. [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.

The combined work of Bousquet-Mélou, Claesson, Dukes, Jelínek, Kitaev, Kubitzke and Parviainen has resulted in non-trivial bijections among ascent sequences, (2+2)-free posets, upper-triangular integer matrices, and pattern-avoiding permutations. To probe the finer behaviour of these bijections, we study two types of restrictions on ascent sequences. These restrictions are motivated by our results that their images under the bijections are natural and combinatorially significant. In addition, for one restriction, we are able to determine the effect of poset duality on the corresponding ascent sequences, matrices and permutations, thereby answering a question of the first author and Parviainen in this case. The second restriction should appeal to Catalaniacs. [ABSTRACT FROM AUTHOR]

A poset P = (X , ≺) has an interval representation if each x ∈ X can be assigned a real interval I x so that x ≺ y in P if and only if I x lies completely to the left of I y. Such orders are called interval orders. In this paper we give a surprisingly simple forbidden poset characterization of those posets that have an interval representation in which each interval length is either 0 or 1. In addition, for posets (X , ≺) with a weight of 1 or 2 assigned to each point, we characterize those that have an interval representation in which for each x ∈ X the length of the interval assigned to x equals the weight assigned to x. For both problems we can determine in polynomial time whether the desired interval representation is possible and in the affirmative case, produce such a representation. [ABSTRACT FROM AUTHOR]

A representation of interval orders by sequences of antichains is discussed, and its relationship to the Fishburn's representation by sequences of the beginnings and endings of domain elements is analysed in detail. Moreover, an operational semantics based on sequences of maximal antichains is proposed and investigated for a general class of safe Petri nets with context arcs. [ABSTRACT FROM AUTHOR]

We show that the protocol complex formalization of fault-tolerant protocols can be directly derived from a suitable semantics of the underlying synchronization and communication primitives, based on a geometrization of the state space. By constructing a one-to-one relationship between simplices of the protocol complex and (di)homotopy classes of (di)paths in the latter semantics, we describe a connection between these two geometric approaches to distributed computing: protocol complexes and directed algebraic topology. This is exemplified on atomic snapshot, iterated snapshot and layered immediate snapshot protocols, where a well-known combinatorial structure, interval orders, plays a key role. We believe that this correspondence between models will extend to proving impossibility results for much more intricate fault-tolerant distributed architectures. [ABSTRACT FROM AUTHOR]

The niche graph of a digraph D is the (simple undirected) graph which has the same vertex set as D and has an edge between two distinct vertices x and y if and only if N+D(x) ∩ N+D(y) ≠ ∅ or N−D(x) ∩ N−D(y) ≠ ∅, where N+D(x) (resp. N−D(x)) is the set of out-neighbors (resp. in-neighbors) of x in D. A digraph D = (V,A) is called a semiorder (or a unit interval order ) if there exist a real-valued function f : V → R on the set V and a positive real number δ ∈ R such that (x, y) ∈ A if and only if f(x) > f(y)+δ. A digraph D = (V,A) is called an interval order if there exists an assignment J of a closed real interval J(x) ⊂ R to each vertex x ∈ V such that (x, y) ∈ A if and only if min J(x) > max J(y). Kim and Roberts characterized the competition graphs of semiorders and interval orders in 2002, and Sano characterized the competition-common enemy graphs of semiorders and interval orders in 2010. In this note, we give characterizations of the niche graphs of semiorders and interval orders

Disanto, Ferrari, Pinzani and Rinaldi have introduced the concept of Catalan pair , which is a pair of partial orders ( S , R ) satisfying certain axioms. They have shown that Catalan pairs provide a natural description of objects belonging to several classes enumerated by Catalan numbers. In this paper, we first introduce another axiomatic structure ( T , R ) , which we call the Catalan pair of type 2 , which describes certain Catalan objects that do not seem to have an easy interpretation in terms of the original Catalan pairs. We then introduce Fishburn triples , which are relational structures obtained as a direct common generalization of the two types of Catalan pairs. Fishburn triples encode, in a natural way, the structure of objects enumerated by the Fishburn numbers, such as interval orders or Fishburn matrices. This connection between Catalan objects and Fishburn objects allows us to associate known statistics on Catalan objects with analogous statistics of Fishburn objects. As our main result, we then show that several known equidistribution results on Catalan statistics can be generalized to analogous results for Fishburn statistics. [ABSTRACT FROM AUTHOR]

In this paper a new criterion for comparing measurement results and determining conformity with specifications is proposed, which essentially is a strategy of estimating the empirical relationships of objects. Comparing with traditional methods given in GUM: 2008 and ISO 14253-1, this criterion improves the resolution of comparison by reducing the sizes of the coverage intervals to be compared. Interval order (a binary relation) is used for comparing the coverage intervals of the measurand and represents the empirical relations. The systematic effects of measurement are classified into two types: monotonic and non-monotonic effects, so that, without correcting the monotonic effects, a biased measurand can be specified to represent the empirical relations. Thereby the uncertainty components arising from the monotonic effects can be removed from the combined uncertainty. A strategy is given for determining the relationships among measurement results and specification limits. An example is given to demonstrate the application of the criterion. [ABSTRACT FROM AUTHOR]

A NaP-preference (necessary and possible preference) on a set A is a pair ${\left(\succsim^{^{_N}}\!,\,\succsim^{^{_P}}\!\right)}$ of binary relations on A such that its necessary component ${\succsim^{^{_N}} \!\!}$ is a partial preorder, its possible component ${\succsim^{^{_P}} \!\!}$ is a completion of ${\succsim^{^{_N}} \!\!}$, and the two components jointly satisfy natural forms of mixed completeness and mixed transitivity. We study additional mixed transitivity properties of a NaP-preference ${\left(\succsim^{^{_N}}\!,\,\succsim^{^{_P}}\!\right)}$, which culminate in the full transitivity of its possible component ${\succsim^{^{_P}} \!\!}$. Interval orders and semiorders are strictly related to these properties, since they are the possible components of suitably transitive NaP-preferences. Further, we introduce strong versions of interval orders and semiorders, which are characterized by enhanced forms of mixed transitivity, and use a geometric approach to compare them to other well known preference relations. [ABSTRACT FROM AUTHOR]

The niche graph of a digraph D is the (simple undirected) graph which has the same vertex set as D and has an edge between two distinct vertices x and y if and only if N+D (x) ∩ N+D (y) ≠ Ø or N-D (x) ∩ N-D (y) ≠ Ø, where N+D (x) (resp. N-D (x)) is the set of out-neighbors (resp. in-neighbors) of x in D. A digraph D = (V,A) is called a semiorder (or a unit interval order ) if there exist a real-valued function ƒ: V → ℝon the set V and a positive real number δ ∈ ℝ such that (x, y) ∈ A if and only if ƒ(x) > ƒ(y) + δ. A digraph D = (V,A) is called an interval order if there exists an assignment J of a closed real interval J(x) ⊂ ℝ to each vertex x ∈ V such that (x, y) ∈ A if and only if min J(x) > max J(y). Kim and Roberts characterized the competition graphs of semiorders and interval orders in 2002, and Sano characterized the competition-common enemy graphs of semiorders and interval orders in 2010. In this note, we give characterizations of the niche graphs of semiorders and interval orders. [ABSTRACT FROM AUTHOR]

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]