Spherical containment and the Minkowski dimension of partial orders

The recent work on circle orders generalizes to higher dimensional spheres. As spherical containment is equivalent to causal precedence in Minkowski space, we define the Minkowski dimension of a poset to be the dimension of the minimal Minkowski space into which the poset can be embedded; this isd if the poset can be represented by containment with spheresS ^d–2 and of no lower dimension. Comparing this dimension with the standard dimension of partial orders we prove that they are identical in dimension two but not in higher dimensions, while their irreducible configurations are the same in dimensions two and three. Moreover, we show that there are irreducible configurations for arbitrarily large Minkowski dimension, thus providing a lower bound for the Minkowski dimension of partial orders.     

Circle orders and angle orders

A poset is a circle order if its points can be mapped into circular disks in the plane so that x in the poset precisely when x's circular disk is properly included in y's; the poset is an angle order if its points can be mapped into unbounded angular regions that preserve < by proper inclusion. It is well known that many finite angle orders are not circle orders, but has been open as to whether every finite circle order is an angle order. This paper proves that there are finite circle orders that are not angle orders.     

Angle orders

A finite poset is an angle order if its points can be mapped into angular regions in the plane so thatx precedesy in the poset precisely when the region forx is properly included in the region fory. We show that all posets of dimension four or less are angle orders, all interval orders are angle orders, and that some angle orders must have an angular region less than 180° (or more than 180°). The latter result is used to prove that there are posets that are not angle orders.The smallest verified poset that is not an angle order has 198 points. We suspect that the minimum is around 30 points. Other open problems are noted, including whether there are dimension-5 posets that are not angle orders.Research supported in part by the National Science Foundation, grant number DMS-8401281.     

Angle orders and zeros

An angle order is a partially ordered set whose points can be mapped into unbounded angular regions in the plane such that x is less than y in the partial order if and only if x's angular region is properly included in y's. The zero augmentation of a partially ordered set adds one point to the set that is less than all original points. We prove that there are finite angle orders whose augmentations are not angle orders. The proof makes extensive use of Ramsey theory.     

Combinatorial representation and convex dimension of convex geometries

We develop a representation theory for convex geometries and meet distributive lattices in the spirit of Birkhoff's theorem characterizing distributive lattices. The results imply that every convex geometry on a set X has a canonical representation as a poset labelled by elements of X. These results are related to recent work of Korte and Lovász on antimatroids. We also compute the convex dimension of a convex geometry.Supported in part by NSF grant no. DMS-8501948.     

N-free orders and minimal interval extensions

We investigate problems related to the set of minimal interval extensions of N-free orders. This leads us to a correspondence between this set for an arbitrary order and a certain set of its maximal N-free reductions. We also get a 1-1-correspondence between the set of linear extensions of an arbitrary order and the set of minimal interval extensions of the linegraph of that order. This has an algorithmic consequence, namely the problem of counting minimal interval extensions of an N-free order is #P-complete. Finally a characterization of all N-free orders with isomorphic root graph is given in terms of their lattice of maximal antichains; the lattices are isomorphic iff the root graphs agree.This work was supported by the PROCOPE Program. The first author is supported by the DFG.     

E-convex infix codes

Two partial orders that play an important role in the combinatorics of words, can be defined in a natural way on the free monoid X ^* generated by the finite alphabet X: the infix and the embedding orders. A set C of nonempty words is called an infix code (hypercode) over X if C is an antichain with respect to the infix (embedding) order. A set of words is said to be e-convex if it is convex with respect to the embedding order. Two characterizations of the e-convex infix codes are given as well as a sufficient condition for such codes to be finite. It is shown that the family EIC(X) of the e-convex infix codes with the empty word forms, under the operation of concatenation, a free submonoid of the free monoid B(X) of the biprefix codes and that the generating alphabet of EIC(X) is a sub-alphabet of the generating alphabet of B(X).This research was supported by Grant A7877 of the Natural Sciences and Engineering Council of Canada.     

On the conductance of order Markov chains

Let Q be a convex solid in ⁿ , partitioned into two volumes u and v by an area s. We show that s>min(u,v)/diam Q, and use this inequality to obtain the lower bound n ^-5/2 on the conductance of order Markov chains, which describe nearly uniform generators of linear extensions for posets of size n. We also discuss an application of the above results to the problem of sorting of posets.Computing Center of the USSR Academy of Sciences USSR     

Angle orders,regular n-gon orders and the crossing number

A finite poset P(X,<) on a set X={ x ₁,...,x _m} is an angle order (regular n-gon order) if the elements of P(X,<) can be mapped into a family of angular regions on the plane (a family of regular polygons with n sides and having parallel sides) such that x _ij if and only if the angular region (regular n-gon) for x _i is contained in the region (regular n-gon) for x _j. In this paper we prove that there are partial orders of dimension 6 with 64 elements which are not angle orders. The smallest partial order previously known not to be an angle order has 198 elements and has dimension 7. We also prove that partial orders of dimension 3 are representable using equilateral triangles with the same orientation. This results does not generalizes to higher dimensions. We will prove that there is a partial order of dimension 4 with 14 elements which is not a regular n-gon order regardless of the value of n. Finally, we prove that partial orders of dimension 3 are regular n-gon orders for n3.This research was supported by the Natural Sciences and Engineering Research Council of Canada, grant numbers A0977 and A2415.     

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 Boolean dimension of spherical orders

It is well known that if a planar order P is bounded, i.e. has only one minimum and one maximum, then the dimension of P (LD(P)) is at most 2, and if we remove the restriction that P has only one maximum then LD(P)3. However, the dimension of a bounded order drawn on the sphere can be arbitrarily large.The Boolean dimension BD(P) of a poset P is the minimum number of linear orders such that the order relation of P can be written as some Boolean combination of the linear orders. We show that the Boolean dimension of bounded spherical orders is never greater than 4, and is not greater than 5 in the case the poset has more than one maximal element, but only one minimum. These results are obtained by a characterization of spherical orders in terms of containment between circular arcs.Part of this work was carried out while both authors were visiting the Department of Applied Mathematics (KAM) of Charles University, Prague. The authors acknowledge support from the EU HCM project DONET.     

Treewidth of cocomparability graphs and a new order-theoretic parameter

We show that the pathwidth of a cocomparability graphG equals its treewidth. The proof is based on a new notion, calledinterval width, for a partial orderP, which is the smallest width of an interval order contained inP, and which is shown to be equal to the treewidth of its cocomparability graph. We observe also that determining any of these parameters isNP-hard and we establish some connections between classical dimension notions of partial orders and interval width. In fact we develop approximation algorithms for interval width ofP whose performance ratios depend on the dimension and interval dimension ofP, respectively.This work was done while the second author stayed at the LIRMM within the PROCOPE program of the DAAD. Both authors acknowledge the support by the PROCOPE program. The second author also acknowledges partial support by the Deutsche Forschungsgemeinschaft under Grant No Mo446/3-1.     

On trees and tree dimension of ordered sets

We call an ordered set (X, ) a tree if no pair of incomparable elements ofX has an upper bound. It is shown that there is a natural way to associate a tree (T, ) with any ordered set (X, ), and (T, ) can be characterized by a universal property. We define the tree dimensiontd(X, ) of an ordered set as the minimal number of extensions of (X, ) which are trees such that the given order is the intersection of those tree orders. We give characterizations of the tree dimension, relations between dimension and tree dimension, and removal theorems.     

Subdifferentiation of monotone functions from semilattices to distributive lattices

An abstract algebraic interpretation of subgradients of real-valued convex functions is presented, and the definition is extended to modal theory. The main result is that a convex (i.e., monotone) function from a semilattice to acomplete distributive lattice is the join of its set of subgradients.     

The convexity lattice of a poset

The authors investigate the lattice Co(P) of convex subsets of a general partially ordered set P. In particular, they determine the conditions under which Co(P) and Co(Q) are isomorphic; and give necessary and sufficient conditions on a lattice L so that L is isomorphic to Co(P) for some P.     

Circle orders,N-gon orders and the crossing number

Let ={P ₁,...,P _m } be a family of sets. A partial order P(, <) on is naturally defined by the condition P _i <P _j iff P _i is contained in P _j . When the elements of are disks (i.e. circles together with their interiors), P(, <) is called a circle order; if the elements of are n-polygons, P(, <) is called an n-gon order. In this paper we study circle orders and n-gon orders. The crossing number of a partial order introduced in [5] is studied here. We show that for every n, there are partial orders with crossing number n. We prove next that the crossing number of circle orders is at most 2 and that the crossing number of n-gon orders is at most 2n. We then produce for every n4 partial orders of dimension n which are not circle orders. Also for every n>3, we prove that there are partial orders of dimension 2n+2 which are not n-gon orders. Finally, we prove that every partial order of dimension 2n is an n-gon order.This research was supported under Natural Sciences and Engineering Research Council of Canada (NSERC Canada) grant numbers A2507 and A0977.     

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     

Convex partitions of a finite lattice

The purpose of this paper is to introduce the lattice of convex partitions for a lattice L. Then we will show some properties of this lattice. Finally, we will show that if the convex partition lattice of L is finite and modular if and only if L is a finite chain. Presented by R. McKenzie. Received December 16, 2004; accepted in final form March 7, 2006.     

A family of (n−1)! Diagonal polynomial orders ofN n

Letn>0 be an element of the setN of nonnegative integers, and lets(x)=x ₁+...+x _n , forx=(x ₁, ...,x _n ) N _n . Adiagonal polynomial order inN _n is a bijective polynomialp:N _n N (with real coefficients) such that, for allx,y N _n ,p(x)<p(y) whenevers(x)<s(y). Two diagonal polynomial orders areequivalent if a relabeling of variables makes them identical. For eachn, Skolem (1937) found a diagonal polynomial order. Later, Morales and Lew (1992) generalized this polynomial order, obtaining a family of 2 ^n–2 (n>1) inequivalent diagonal polynomial orders. Here we present, for eachn>0, a family of (n – 1)! diagonal polynomial orders, up to equivalence, which contains the Morales and Lew diagonal orders.     

Generalizing semidistributivity

A latticeL is called congruence normal if it can be generated by doubling of convex sets starting with the one-element lattice. In the special case of intervals, the lattice is called bounded. It has been proven thatL is bounded if and only ifL is congruence normal and semidistributive.In this paper we study the connection between certain classes of convex sets and generalized semidistributive laws. These so-called doubling classes are pseudovarieties which can be described by implications as well as by forbiden substructures. In the end, we examine the structure of the lattice of all doubling classes.