Balancing extensions via Brunn-Minkowski

We give a simple proof, based on the Brunn-Minkowski Theorem, of Theorem. Inany finite poset P not a total order there are elementsx, y such that

A note on merging

For a finite poset P and x, yP let pr(x>y) be the fraction of linear extensions which put x above y. N. Linial has shown that for posets of width 2 there is always a pair x, y with 1/3 pr(x>y)2/3. The disjoint union C ₁C ₂ of a 1-element chain with a 2-element chain shows that the bound 1/3 cannot be further increased. In this paper the extreme case is characterized: If P is a poset of width 2 then the bound 1/3 is exact iff P is an ordinal sum of C ₁C ₂'s and C ₁'s.     

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.     

The poset of closures as a model of changing databases

The combinatorial properties of the poset of closures are studied, especially the degrees in the Hasse diagram.The research of these authors was supported by the Hungarian National Foundation for Scientific Research, grant numbers 1812 and 700021.     

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.     

On computing the number of linear extensions of a tree

An algorithm requiring O(n ²) arithmetic operations for computing the number of linear extensions of a poset whose covering graph is a tree is given.This research was partially funded by the National Science and Engineering Research Council of Canada under Grant Number A4219.     

The minimum of the antichains in the factor poset

Denote g(m, n) the minimum of min A, where A is a subset of {1, 2, ..., m} of size n and there do not exist two distinct x and y in A such that x divides y. We use a method of poset to prove that g(m, n)=2 ⁱ for positive integer ilog₃ m and 1+s(m, i–1), where s(m, i) is the number of odd integers x such that m/3 ⁱ .Research was supported by National Science Council of Republic of China under Grant NSC74-0201-M008d-02.     

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.     

NP-completeness properties about linear extensions

Following the pioneering work of Kierstead, we present here some complexity results about the construction of depth-first greedy linear extensions. We prove that the recognition of Dilworth partially ordered sets of height 2, as defined by Syslo, is NP-complete. This last result yields a new proof of the NP-completeness of the jump number problem, first proved by Pulleyblank.     

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.     

Counting linear extensions

We survey the problem of counting the number of linear extensions of a partially ordered set. We show that this problem is #P-complete, settling a long-standing open question. This result is contrasted with recent work giving randomized polynomial-time algorithms for estimating the number of linear extensions.One consequence of our main result is that computing the volume of a rational polyhedron is strongly #P-hard. We also show that the closely related problems of determining the average height of an element x of a give poset, and of determining the probability that x lies below y in a random linear extension, are #P-complete.Research carried out while this author was visiting Bellcore under the auspices of DIMACS.     

The recursive structure of some ordering problems

Some classical ordering problems (sorting, finding the maximum, finding the maximum and the minimum, finding the largest and the next largest, merging, and finding the median) are considered from a recursive viewpoint. IfX(n) denotes an instance of sizen of any one of these problems thenX(n) can be solved by finding the solution to a number (n,k) of problemsX(k) for some fixedk; (nk,k) is called therelative complexity. Upper and lower bounds on the relative complexity are found. For the problem of finding the maximum, finding the maximum and the minimum, and finding the largest and the next largest these bounds are optimal.     

On the width of an orientation of a tree

There are 2 ^n-1 ways in which a tree on n vertices can be oriented. Each of these can be regarded as the (Hasse) diagram of a partially ordered set. The maximal and minimal widths of these posets are determined. The maximal width depends on the bipartition of the tree as a bipartite graph and it can be determined in time O(n). The minimal width is one of [/2] or [/2]+1, where is the number of leaves of the tree. An algorithm of execution time O(n + ² log ) to construct the minimal width orientation is given.This research was partially funded by the National Science and Engineering Research Council of Canada under Grant Number A4219.     

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.     

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.     

Regressions and monotone chains II: The poset of integer intervals

A regressive function (also called a regression or contractive mapping) on a partial order P is a function mapping P to itself such that (x)x. A monotone k-chain for is a k-chain on which is order-preserving; i.e., a chain x ₁<...ksuch that (x ₁)...(x_k). Let P _nbe the poset of integer intervals {i, i+1, ..., m} contained in {1, 2, ..., n}, ordered by inclusion. Let f(k) be the least value of n such that every regression on P _nhas a monotone k+1-chain, let t(x,j) be defined by t(x, 0)=1 and t(x,j)=x ^t(x,j–1). Then f(k) exists for all k (originally proved by D. White), and t(2,k) < f(K) <t( + _k, k) , where _k 0 as k. Alternatively, the largest k such that every regression on P _nis guaranteed to have a monotone k-chain lies between lg^*(n) and lg^*(n)–2, inclusive, where lg^*(n) is the number of appliations of logarithm base 2 required to reduce n to a negative number. Analogous results hold for choice functions, which are regressions in which every element is mapped to a minimal element.     

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.     

Alternating cycle-free matchings

The investigation of alternating cycle-free matchings is motivated by the Jump-number problem for partially ordered sets and the problem of counting maximum cardinality matchings in hexagonal systems.We show that the problem of deciding whether a given chordal bipartite graph has an alternating cycle-free matching of a given cardinality is NP-complete. A weaker result, for bipartite graphs only, has been known for some time. Also, the alternating cycle-free matching problem remains NP-complete for strongly chordal split graphs of diameter 2.In contrast, we give algorithms to solve the alternating cycle-free matching problem in polynomial time for bipartite distance hereditary graphs (time O(m ²) on graphs with m edges) and distance hereditary graphs (time O(m ⁵)).     

Constructing greedy linear extensions by interchanging chains

A natural way to prove that a particular linear extension of an ordered set is ‘optimal’ with respect to the ‘jump number’ is to transform this linear extension ‘canonically’ into one that is ‘optimal’. We treat a ‘greedy chain interchange’ transformation which has applications to ordered sets for which each ‘greedy’ linear extension is ‘optimal’.