Partial Orders on Weak Orders Convex Subsets

We study a visibility relation on the nonempty connected convex subsets of a finite partially ordered set and we investigate the partial orders representable as a visibility relation of such subsets of a weak order. Moreover, we consider restrictions where the subsets of the weak order are total orders or isomorphic total orders.     

Median orders of tournaments: A tool for the second neighborhood problem and Sumner's conjecture

We give a short constructive proof of a theorem of Fisher: every tournament contains a vertex whose second outneighborhood is as large as its first outneighborhood. Moreover, we exhibit two such vertices provided that the tournament has no dominated vertex. The proof makes use of median orders. A second application of median orders is that every tournament of order 2n − 2 contains every arborescence of order n > 1. This is a particular case of Sumner's conjecture: every tournament of order 2n − 2 contains every oriented tree of order n > 1. Using our method, we prove that every tournament of order (7n − 5)/2 contains every oriented tree of order n. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 244–256, 2000     

Flippable Pairs and Subset Comparisons in Comparative Probability Orderings

We show that every additively representable comparative probability order on n atoms is determined by at least n–1 binary subset comparisons. We show that there are many orders of this kind, not just the lexicographic order. These results provide answers to two questions of Fishburn et al. (Math. Oper. Res. 27:227–243, 2002). We also study the flip relation on the class of all comparative probability orders introduced by Maclagan. We generalise an important theorem of Fishburn, Pekeč and Reeds, by showing that in any minimal set of comparisons that determine a comparative probability order, all comparisons are flippable. By calculating the characteristics of the flip relation for n=6 we discover that the polytopes associated with the regions in the corresponding hyperplane arrangement can have no more than 13 facets and that there are 20 regions whose associated polytopes have 13 facets. All the neighbours of the 20 comparative probability orders which correspond to those regions are representable. Research partially supported by the N.Z. Centres of Research Excellence Fund (grant UOA 201).     

Note: An algorithm to solve polyhedral convex set optimization problems

We provide a counterexample to the remark in Löhne and Schrage [An algorithm to solve polyhedral convex set optimization problems, Optimization 62 (2013), pp. 131-141] that every solution of a polyhedral convex set optimization problem is a pre-solution. A correct statement is that every solution of a polyhedral convex set optimization problem obtained by the algorithm SetOpt is a pre-solution. We also show that every finite infimizer and hence every solution of a polyhedral convex set optimization problem contains a pre-solution.     

Analyzing the effect of the inventory policy on order and inventory variability with linear control theory

In this paper we apply linear control theory to study the effect of various inventory policies on order and inventory variability, which are key drivers of supply chain performance. In particular, we study a two-echelon supply chain with a stationary demand pattern under the influence of three inventory policies: an inventory-on-hand policy that bases orders on the visible inventory at an installation, an installation-stock policy that bases orders on the inventory position (on-hand plus on-order inventory) at an installation, and an echelon-stock policy that bases orders on the inventory position at that installation and all downstream installations. We prove analytically that the inventory-on-hand policy is unstable in practical settings, confirming analytically what has been observed in experimental settings and in practice. We also prove that the installation-stock and echelon-stock policies are stable and analyze their effect on order and inventory fluctuation. Specifically, we show the general superiority of the echelon-stock in our setting and demonstrate analytically the effect of forecasting parameters on order and inventory fluctuations, confirming the results in other research.     

On topological properties of ultraproducts of finite sets

In [3] a certain family of topological spaces was introduced on ultraproducts. These spaces have been called ultratopologies and their definition was motivated by model theory of higher order logics. Ultratopologies provide a natural extra topological structure for ultraproducts. Using this extra structure in [3] some preservation and characterization theorems were obtained for higher order logics. The purely topological properties of ultratopologies seem interesting on their own right. We started to study these properties in [2], where some questions remained open. Here we present the solutions of two such problems. More concretely we show 1. that there are sequences of finite sets of pairwise different cardinalities such that in their certain ultraproducts there are homeomorphic ultratopologies and 2. if A is an infinite ultraproduct of finite sets, then every ultratopology on A contains a dense subset D such that |D| < |A|. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On a Possible Continuous Analogue of the Szpilrajn Theorem and its Strengthening by Dushnik and Miller

The Szpilrajn theorem and its strengthening by Dushnik and Miller belong to the most quoted theorems in many fields of pure and applied mathematics as, for instance, order theory, mathematical logic, computer sciences, mathematical social sciences, mathematical economics, computability theory and fuzzy mathematics. The Szpilrajn theorem states that every partial order can be refined or extended to a total (linear) order. The theorem by Dushnik and Miller states, moreover, that every partial order is the intersection of its total (linear) refinements or extensions. Since in mathematical social sciences or, more general, in any theory that combines the concepts of topology and order one is mainly interested in continuous total orders or preorders in this paper some aspects of a possible continuous analogue of the Szpilrajn theorem and its strengthening by Dushnik and Miller will be discussed. In particular, necessary and sufficient conditions for a topological space to satisfy a possible continuous analogue of the Dushnik-Miller theorem will be presented. In addition, it will be proved that a continuous analogue of the Szpilrajn theorem does not hold in general. Further, necessary and in some cases necessary and sufficient conditions for a topological space to satisfy a possible continuous analogue of the Szpilrajn theorem will be presented.      

Linear Orders on General Algebras

We answer the question, when a partial order in a partially ordered algebraic structure has a compatible linear extension. The finite extension property enables us to show, that if there is no such extension, then it is caused by a certain finite subset in the direct square of the base set. As a consequence, we prove that a partial order can be linearly extended if and only if it can be linearly extended on every finitely generated subalgebra. Using a special equivalence relation on the above direct square, we obtain a further property of linearly extendible partial orders. Imposing conditions on the lattice of compatible quasi orders, the number of linear orders can be determined. Our general approach yields new results even in the case of semi-groups and groups.     

Computing maximal chains

In (Fund Math 60:175–186 1967), Wolk proved that every well partial order (wpo) has a maximal chain; that is a chain of maximal order type. (Note that all chains in a wpo are well-ordered.) We prove that such maximal chain cannot be found computably, not even hyperarithmetically: No hyperarithmetic set can compute maximal chains in all computable wpos. However, we prove that almost every set, in the sense of category, can compute maximal chains in all computable wpos. Wolk’s original result actually shows that every wpo has a strongly maximal chain, which we define below. We show that a set computes strongly maximal chains in all computable wpo if and only if it computes all hyperarithmetic sets.     

Finiteness Theorems for Graphs and Posets Obtained by Compositions

We investigate classes of graphs and posets that admit decompositions to obtain or disprove finiteness results for obstruction sets. To do so we develop a theory of minimal infinite antichains that allows us to characterize such antichains by means of the set of elements below it.In particular we show that the following classes have infinite antichains with respect to the induced subgraph/poset relation: interval graphs and orders, N-free orders, orders with bounded decomposition width. On the other hand for orders with bounded decomposition diameter finiteness of all antichains is shown. As a consequence those classes with infinite antichains have undecidable hereditary properties whereas those with finite antichains have fast algorithms for all such properties.     

Some progress on the Aharoni–Korman conjecture

Aharoni and Korman (Order 9 (1992) 245) have conjectured that every ordered set without infinite antichains possesses a chain and a partition into antichains so that each part intersects the chain. Related to both Aharoni's extension of the König duality theorem and Dilworth's theorem, this is an important conjecture in the theory of infinite orders. It is verified for ordered sets of the form C×P, where C is a chain and P is finite, and for ordered sets with no infinite antichains and no infinite intervals.     

Crowns,cutsets, and valuable partial orders

We consider the problem of recognizing those partial orders which admit a valuation: this is a linear-algebraic condition which arises naturally in an algebraic/geometric context. We show that a partial order has at most one valuation (which is integer-valued) and present various structural conditions which are either necessary or sufficient for a partial order to be valuable. The first main result is a reduction theorem which allows us to restrict attention to those partial orders which do not have a bounded cutset. We use this and a theorem of Kelly and Rival to prove the second main result: that every contraction of a bounded partial order is fibre-valuable if and only if the partial order is a dismantlable lattice. This result has a geometric interpretation.This research was supported by the Natural Sciences and Engineering Research Council of Canada under operating grant OGP0105392.     

On a Strong Continuous Analogue of the Szpilrajn Theorem and its Strengthening by Dushnik and Miller

The Szpilrajn theorem states that every (partial) order has a total (linear) refinement or extension by a total (linear) order. Its strengthening by Dushnik and Miller states, moreover, that every (partial) order is the intersection of its total (linear) refinements or extensions. In any theory that combines the concepts of topology and order, however, one is interested in (weakly) continuous orders. Therefore, in this paper the question will be answered, if the Szpilrajn theorem and its strengthening by Dushnik and Miller respectively can be generalized in such a way that they also include the case that (weakly) continuous orders are considered. Since arbitrary preorders are not considered in this paper we speak of possible strong continuous analogues of the Szpilrajn theorem and its strengthening by Dushnik and Miller. The main results of this paper show that the Dushnik–Miller theorem cannot be generalized to the (weakly) continuous case while the Szpilrajn theorem at least in very particular situations allows generalizations to the case that (weakly) continuous orders are considered. Finally, also a strong semicontinuous analogue of the Szpilrajn theorem and its strengthening by Dushnik and Miller will be discussed.     

An Ordered Set of Size ℵ1 with Monochromatic Maximal Chains

Every model of ZFC contains a product of two linear orders, each of size ₁, with the property that every subset or complement thereof contains a maximal chain.     

Negative Dense Linear Orders

Considering dense linear orders, we establish their negative representability over every infinite negative equivalence, as well as uniformly computable separability by computable gaps and the productivity of the set of computable sections of their negative representations. We construct an infinite decreasing chain of negative representability degrees of linear orders and prove the computability of locally computable enumerations of the field of rational numbers.     

Feasibility principles for Downstream Demand Inference in supply chains

Many companies are adopting strategies that enable Demand Information Sharing (DIS) between the supply chain links. Recently, a steady stream of research has identified mathematical relationships between demands and orders at any link in the supply chain. Based on these relationships and strict model assumptions, it has been suggested that the upstream member can infer the demand at the downstream member from their orders. If this is so, DIS will be of no value. In this paper, we argue that real-world modelling requires less restrictive assumptions. We present Feasibility Principles to show that it is not possible for an upstream member to accurately infer consumer demand under more realistic model assumptions. Thus, we conclude that DIS has value in supply chains. We then move our focus to the supply chain model assumptions in the papers arguing that there is value in sharing demand information. Using a simulation experiment, we show that the value of sharing demand information in terms of inventory reductions will increase under more realistic supply chain model assumptions.     

Universal gradings of orders

For commutative rings, we introduce the notion of a universal grading, which can be viewed as the “largest possible grading”. While not every commutative ring (or order) has a universal grading, we prove that every reduced order has a universal grading, and this grading is by a finite group. Examples of graded orders are provided by group rings of finite abelian groups over rings of integers in number fields. We also generalize known properties of nilpotents, idempotents, and roots of unity in such group rings to the case of graded orders; this has applications to cryptography. Lattices play an important role in this paper; a novel aspect is that our proofs use that the additive group of any reduced order can in a natural way be equipped with a lattice structure.     

Extending a Partially Ordered Set: Links with its Lattice of Ideals

A well-known result of Bonnet and Pouzet bijectively links the set of linear extensions of a partial order P with the set of maximal chains of its lattice of ideals I(P). We extend this result by showing that there is a one-to-one correspondence between the set of all extensions of P and the set of all sublattices of I(P) which are chain-maximal in the sense that every chain which is maximal (for inclusion) in the sublattice is also maximal in the lattice.We prove that the absence of order S as a convex suborder of P is equivalent to the absence of I(S) as a convex suborder of I(P). Let S be a set of partial orders and let us call S-convex-free any order that does not contain any order of S as a convex suborder. We deduce from the previous results that there is a one-to-one correspondence between the set of S-convex-free extensions of P and the set of I(S)-convex-free chain-maximal sublattices of I(P). This can be applied to some classical classes of orders (total orders and in the finite case, weak orders, interval orders, N-free orders). In the particular case of total orders this gives as a corollary the result of Bonnet and Pouzet.     

A collaborative decentralized distribution system with demand forecast updates

In this paper, we study inventory pooling coalitions within a decentralized distribution system consisting of a manufacturer, a warehouse (or an integration center), and n retailers. At the time their orders are placed, the retailers know their demand distribution but do not know the exact value of the demand. After certain production and transportation lead time elapses, the orders arrive at the warehouse. During this time, the retailers can update their demand forecasts.We first focus on cooperation among the retailers - the retailers coordinate their initial orders and can reallocate their orders in the warehouse after they receive more information about their demand and update their demand forecasts. We study two types of cooperation: forecast sharing and joint forecasting. By using an example, we illustrate how forecast sharing collaboration might worsen performance, and asymmetric forecasting capabilities of the retailers might harm the cooperation. However, this does not happen if the retailers possess symmetric forecasting capabilities or they cooperate by joint forecasting, and the associated cooperative games have non-empty cores.Finally, we analyze the impact that cooperation and non-cooperation of the retailers has on the manufacturer’s profit. We focus on coordination of the entire supply chain through a three-parameter buyback contract. We show that our three-parameter contract can coordinate the system if the retailers have symmetric margins. Moreover, under such a contract the manufacturer benefits from retailers’ cooperation since he can get a share of improved performance.     

A Ramsey theorem for multiposets

In the parlance of relational structures, the Finite Ramsey Theorem states that the class of all finite chains has the Ramsey property. A classical result from the 1980s claims that the class of all finite posets with a linear extension has the Ramsey property. In 2010 Sokić proved that the class of all finite structures consisting of several linear orders has the Ramsey property. This was followed by a 2017 result of Solecki and Zhao that the class of all finite posets with several linear extensions has the Ramsey property.Using the categorical reinterpretation of the Ramsey property in this paper we prove a common generalization of all these results. We consider multiposets to be structures consisting of several partial orders and several linear orders. We allow partial orders to extend each other in an arbitrary but fixed way, and require that every partial order is extended by at least one of the linear orders. We then show that the class of all finite multiposets conforming to a fixed template has the Ramsey property.