Transitive closure for restricted classes of partial orders

Most papers dealing with partial orders assume that the input is given either in transitively closed or transitively reduced form. In this paper, we show that it is possible to solve some problems on partial orders in less time than it takes to perform transitive closure or reduction for general graphs. In particular, we present efficient algorithms for recognizing two dimensional partial orders and N-free partial orders when no assumptions are made about the form of the input.This work was supported by National Science Foundation Grant DCR-8604577 and the Vanderbilt University Research Council.     

Automorphism groups of comparability and covering graphs

Let G be a group and H a subgroup of G. It is shown that there exists a partially ordered set (X, ) such that G is isomorphic to the group of all automorphisms of the comparability graph of (X, ) and such that under this isomorphism H is mapped onto the group of all order-automorphisms of (X, ). There also exists a partially ordered set (Y, ) such that G is isomorphic to the group of all automorphisms of the covering graph of (Y, ) and such that under this isomorphism H is mapped onto the group of all order-automorphisms of (Y, ). In this representation X and Y can be taken to be finite if G is finite and of the same cardinality as G if G is infinite.     

On minimizing the jump number for interval orders

The purpose of this paper is to give an effective characterization of all interval orders which are greedy with respect to the jump number problem.This research (Math/1406/30) was supported by the Research Center, College of Science, King Saud University, Riyadh, Saudi Arabia.     

Tackling the jump number of interval orders

Although the jump number problem for partially ordered sets in NP-complete in general, there are some special classes of posets for which polynomial time algorithms are known.Here we prove that for the class of interval orders the problem remains NP-complete. Moreover we describe another 3/2-approximation algrithm (two others have been developed already by Felsner and Syslo, respectively) by using a polynomial time subgraph packing algorithm.     

Completion of operator partial matrices associated with chordal graphs

H. Dym and I. Gohberg established in [6] necessary and sufficient conditions for the existence and uniqueness of an invertible block matrix F=(F_ij)_i,j=1,...,n such that F_ij=R_ij for |i–j|m and F^–1 has a band triangular factorization and so (F^–1)_ij=0 for |i–j|>m. Here R_ij, |i–j|m are given block matrices.The aim of this paper is to generalize these results in two directions. First, we shall allow R_ij to be an (linear bounded) operator acting between the Hilbert spaces H_j and H_i. Secondly, the set of indices of the given R_ij will be more general than banded ones. In fact, we will consider index sets which have an associated graph which is chordal. The case of partial positive operator matrices is also discussed.     

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.     

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.     

A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders

Let L=u ₁ , u ₂ , ..., u _k be a linear extension of a poset P. Each pair (u _i , u _i+1 ) of unrelated elements in P is called a jump of L. The jump number problem is to find L with the minimum number of jumps. The problem is known to be NP-hard even on bipartite posets. Here we present a linear time algorithm for it in 2-dimensional bipartite posets. We also discuss briefly some weighted cases.     

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.     

Chaines maximales de préordres

Résumé La famille des préordres sur un ensemble fixé constitue un treillis pour l'inclusion. Répondant à une question rencontrée par S. Eilenberg dans l'étude des automates non déterministes on établit une propriété des chaînes maximales de préordres sur un ensemble fini.On en déduit que si l'ensemble a n éléments, de telles chaînes contiennent au plus [n(n + 1)]/2 préordres.

---

     

Extremal problems for linear orders on [n] p

Let be a product order on [n] ^p i.e. for A, B [n] ^p , 1a ₁<a ₂<...<a _p º-n and 1<-b ₁<b ₂<...<b _p <-n we have AB iff a _i<-b _i for all i=1, 2,..., p. For a linear extension < of (ordering [n] ^p as ) let F _< ^[n],p (m) count the number of A _i 's, i<-m such that 1A _i. Clearly, for every m and <, where <l denotes the lexicographic order on [n] ^p . In this note we prove that the colexicographical order, <c, provides a corresponding lower bound i.e. that holds for any linear extension < of .This project together with [2] was initiated by the first author and continued in colaboration with the second author. After the death of the first author the work was continued and finalized by the second and the third author.Research supported by NSF grant DMS 9011850.     

Planar graphs and poset dimension

We view the incidence relation of a graph G=(V. E) as an order relation on its vertices and edges, i.e. a<_G b if and only of a is a vertex and b is an edge incident on a. This leads to the definition of the order-dimension of G as the minimum number of total orders on V E whose intersection is <_G. Our main result is the characterization of planar graphs as the graphs whose order-dimension does not exceed three. Strong versions of several known properties of planar graphs are implied by this characterization. These properties include: each planar graph has arboricity at most three and each planar graph has a plane embedding whose edges are straight line segments. A nice feature of this embedding is that the coordinates of the vertices have a purely combinatorial meaning.     

Random graph orders

Let P _n be the order determined by taking a random graph G on {1, 2,..., n}, directing the edges from the lesser vertex to the greater (as integers), and then taking the transitive closure of this relation. We call such and ordered set a random graph order. We show that there exist constants c, and °, such that the expected height and set up number of P _n are sharply concentrated around cn and °n respectively. We obtain the estimates: .565<c<.610, and .034<°<.289. We also discuss the width, dimension, and first-order properties of P _n.     

Minimizing bumps in linear extensions of ordered sets

A linear extension x ₁ x ₂ x ₃ ... of a partially ordered set (X, <) has a bump whenever x _i <x _i +1. We examine the problem of determining linear extensions with as few bumps as possible. Heuristic algorithms for approximate bump minimization are considered.     

On the size of jump-critical ordered sets

The maximum size of a jump-critical ordered set with jump-number m is at most (m+1)!     

Greedy linear extensions for minimizing bumps

Let P be a finite poset and let L={x ₁<...n} be a linear extension of P. A bump in L is an ordered pair (x _i , x _i+1) where x _ii+1 in P. The bump number of P is the least integer b(P), such that there exists a linear extension of P with b(P) bumps. We call L optimal if the number of bumps of L is b(P). We call L greedy if x _{i j} for every j>i, whenever (x _i, x _i+1) is a bump. A poset P is called greedy if every greedy linear extension of P is optimal. Our main result is that in a greedy poset every optimal linear extension is greedy. As a consequence, we prove that every greedy poset of bump number k is the linear sum of k+1 greedy posets, each of bump number zero.This research (Math/1406/31) was supported by the Research Center, College of Science, King Saud University, Riyadh, Saudi Arabia.     

Chordal bipartite graphs and crowns

We prove that a bipartite graph is chordal if and only if it has an elimination scheme. This leads to a polynomial algorithm to recognize whether an ordered set is cycle-free.     

The jump number of suborders of the power set order

Let P be an ordered set induced by several levels of a power set. We give a formula for the jump number of P and show that reverse lexicographic orderings of P are optimal. The proof is based on an extremal set result of Frankl and Kalai.     

Greedy posets for the bump-minimizing problem

A bump (x _i,x _i+1) occurs in a linear extension L={x ₁<...n} of a poset P, if x _ii+1 in P. L. is greedy if x _ij for every j>i, whenever (x _i x _i+1) in a bump in L. The purpose of this paper is to give a characterization of all greedy posets. These are the posets for which every greedy linear extension has a minimum number of bumps.This research (Math/1406/31) was supported by the Research Center, College of Science, King Saud University, Riyadh, Saudi Arabia.     

Minimizing the jump number for partially ordered sets: A graph-theoretic approach

The purpose of this paper is to present a graph-theoretic approach to the jump number problem for N-free posets which is based on the observation that the Hasse diagram of an N-free poset is a line digraph. Therefore, to every N-free poset P we can assign another digraph which is the root digraph of the Hasse diagram of P. Using this representation we show that the jump number of an N-free poset is equal to the cyclomatic number of its root digraph and can be found (without producing any linear extension) by an algorithm which tests if a given poset is N-free. Moreover, we demonstrate that there exists a correspondence between optimal linear extensions of an N-free poset and spanning branchings of its root digraph. We provide also another proof of the fact that optimal linear extensions of N-free posets are exactly greedy linear extensions. In conclusion, we discuss some possible generalizations of these results to arbitrary posets.