[2] x [3] x N is not a circle order

The result stated in the title is proved in this note. Actually we show that S x N is not a circle order, where S={(1, 1), (1, 2), (1, 3), (2, 1), (2, 3)}. Furthermore this non-circle order is critical in the sense that (S-{x}) x N is a circle order for any x in S.     

On circle containment orders

A partially ordered set is called acircle containment order provided one can assign to each element of the poset a circle in the plane so thatxy iff the circle assigned tox is contained in the circle assigned toy. It has been conjectured that every finite three-dimensional partially ordered set is a circle containment order. We show that the infinite three dimensional posetZ ³ isnot a circle containment order.Research supported in part by the Office of Naval Research, contract number N00014-85-K0622.Research supported in part by National Science Foundation, grant number DMS-8403646.     

A shellable poset that is not lexicographically shellable

It is known that a lexicographically shellable poset is shellable, and it has been asked whether the two concepts are equivalent. We provide a counterexample, a shellable graded poset that is not lexicographically shellable.     

Interval orders and circle orders

A finite poset is an interval order if its point can be mapped into real intervals so that x in the poset precisely when x's interval lies wholly to the left of y's; the poset is a circle order if its points can be mapped into circular disks in the plane so that x precisely when x's circular disk is properly included in y's. This note proves that every finite interval order is a circle order.     

The spread of a partial order

The deficiency of a partial order is the number of incomparable pairs. Another measure, the spread of a partial order is defined and its relation to the deficiency is established. In certain cases which arise naturally in the analysis of various sorting and selection algorithms where the partial order is only implicitly defined, the spread of the partial order is easier to estimate directly and provides a convenient way to estimate the deficiency.Partially supported by NSF Grant DCR-85-05053.Partially supported by NSF Grant DMS-85-05004.     

The many faces of circle orders

A finite partially ordered set P is called a circle order if one can assign to each x P a circular disk C _x so that xy iff C _x C _y . It is interesting to observe that many other classes of posets, such as space-time orders, parabola orders, the Loewner order for 2×2 Hermitian matrices, etc. turn out to be exactly circle orders (or their higher dimensional analogues). We give a global proof for these equivalences.Research supported in part by the Office of Naval Research, the Air Force Office of Scientific Research and by DIMACS.     

On the greedy dimension of a partial order

This paper introduces a new concept of dimension for partially ordered sets. Dushnik and Miller in 1941 introduced the concept of dimension of a partial order P, as the minimum cardinality of a realizer, (i.e., a set of linear extensions of P whose intersection is P). Every poset has a greedy realizer (i.e., a realizer consisting of greedy linear extensions). We begin the study of the notion of greedy dimension of a poset and its relationship with the usual dimension by proving that equality holds for a wide class of posets including N-free posets, two-dimensional posets and distributive lattices.     

A note on sphere containment orders

Using the ideas of Scheinerman and Wierman [1] and of Hurlbert [2] we give a very short proof that the infinite order [2]×[3]× cannot be represented by containment of Euclidean balls in ad-dimensional space for anyd. Also we give representations of the orders [2]×[2]× and [3]×[3]×[3] by containment of circles in the plane.The work was financially supported by the Russian Foundation of Fundamental Research, Grant 93-011-1486     

A maximal clone of monotone operations which is not finitely generated

There is only one maximal clone on a set of at most eight elements which has not been known to be finitely generated. We show that it is not finitely generated.     

Clones,order varieties,near unanimity functions and holes

A finite ordered set has an order preserving majority function if and only if it is a retract of a direct product of fences.The authors' research was supported by grants from the NSERC of Canada.     

A 3/2-approximation algorithm for the jump number of interval orders

The jump number of a partial order P is the minimum number of incomparable adjacent pairs in some linear extension of P. The jump number problem is known to be NP-hard in general. However some particular classes of posets admit easy calculation of the jump number.The complexity status for interval orders still remains unknown. Here we present a heuristic that, given an interval order P, generates a linear extension , whose jump number is less than 3/2 times the jump number of P.This work was supported by the Deutsche Forschungsgemeinschaft (DFG).     

A note on the dimension of a poset

It is shown that the dimension of a poset is the smallest cardinal number such that there is an embedding of the poset into a strict product of linear orders.     

Generalizations of Tarski's fixed point theorem for order varieties of complete meet semilattices

A poset P is -conditionally complete ( a cardinal) if every set X P all of whose subsets of cardinality < have an upper bound has a least upper bound. For we characterize the subposets of a -complete poset which can occur as the set of fixed points of some montonic function on P. This yields a generalization of Tarski's fixed point theorem. We also show that for every the class of -conditionally complete posets forms an order variety and we exhibit a simple generating poset for each such class.Research supported in part by NSERC while the author was visiting Professor Ivo Rosenberg at the Université de Montreal.Research supported in part by NSF-grant DMS-8703743.     

Degrees of freedom versus dimension for containment orders

Given a family of sets L, where the sets in L admit k degrees of freedom, we prove that not all (k+1)-dimensional posets are containment posets of sets in L. Our results depend on the following enumerative result of independent interest: Let P(n, k) denote the number of partially ordered sets on n labeled elements of dimension k. We show that log P(n, k)nk log n where k is fixed and n is large.Research supported in part by Allon Fellowship and by a grant from Bat Sheva de Rothschild Foundation.Research supported in part by the Office of Naval Research, contract number N00014-85-K0622.     

Weak orders admitting a perpendicular linear order

Two orders on the same set are perpendicular if the constant maps and the identity map are the only maps preserving both orders. We characterize the finite weak orders admitting a perpendicular linear order.     

Semiorders and the 1/3–2/3 conjecture

A well-known conjecture of Fredman is that, for every finite partially ordered set (X, <) which is not a chain, there is a pair of elements x, y such that P(x, the proportion of linear extensions of (X, <) with x below y, lies between 1/3 and 2/3. In this paper, we prove the conjecture in the special case when (X, <) is a semiorder. A property we call 2-separation appears to be crucial, and we classify all locally finite 2-separated posets of bounded width.     

Cover-preserving order embeddings into Boolean lattices

It is not known which finite graphs occur as induced subgraphs of a hypercube. This is relevant in the theory of parallel computing. The ordered version of the problem is: Which finite posets P occur as cover-preserving subposets of a Boolean lattice? Our main Theorem gives (for 0,1-posets) a necessary and sufficient condition, which involves the chromatic number of a graph associated to P. It is applied respectively to upper balanced, meet extremal, meet semidistributive, and semidistributive lattices P. More specifically, we consider isometric embeddings of posets into Boolean lattices. In particular, answering a question of Ivan Rival to the positive, a nontrivial invariant for the covering graph of a poset is found.     

A study of the order dimension of a poset using matrices

In every finite poset (X, ≤) we assign the so called order-matrix , where α_ij ∈ {?2, 0, 1, 2}. Using this matrix, we characterize the order dimension of an arbitrary finite poset.     

A bruhat order for bipartite graphs whose node sets are posets: Lifting,switching, and adding edges

Consider two partially ordered setsP, Q and a number of edges connecting some of the points ofP with some of the points ofQ. This yields a bipartite graph. Some pairs of the edges may cross each other because their endpoints atP andQ are oppositely ordered. A natural decrossing operation is to exchange the endpoints of these edges incident atQ, say. This is called a switch. A left lift of an edge means to replace its starting point atP by a larger starting point. A right lift is defined symmetrically for the endpoints atQ. The operation of adding an edge cannot, informally, be explained better. Assume we are given two bipartite graphs , on the node setPQ. We show that for certain pairs (P, Q) of finite posets, a neat necessary and sufficient criterion can be given in order that is obtainable from by the sequence of elementary operations just defined. A recent characterization of the Bruhat order of the symmetric group follows as a special case.