Diametral Pairs of Linear Extensions

Details Diametral Pairs of Linear Extensions Diametral Pairs of Linear Extensions

2008-09-10

arxiv.org/abs/0809.1828v1

Mathematics

Combinatorics

26 pages, 10 figures

Scientific paper

Given a finite poset P, we consider pairs of linear extensions of P with maximal distance, where the distance between two linear extensions L_1, L_2 is the number of pairs of elements of P appearing in different orders in L_1 and L_2. A diametral pair maximizes the distance among all pairs of linear extensions of P. Felsner and Reuter defined the linear extension diameter of P as the distance between a diametral pair of linear extensions. We show that computing the linear extension diameter is NP-complete in general, but can be solved in polynomial time for posets of width 3. Felsner and Reuter conjectured that, in every diametral pair, at least one of the linear extensions reverses a critical pair. We construct a counterexample to this conjecture. On the other hand, we show that a slightly stronger property holds for many classes of posets: We call a poset "diametrally reversing" if, in every diametral pair, both linear extensions reverse a critical pair. Among other results we show that interval orders and 3-layer posets are diametrally reversing. From the latter it follows that almost all posets are diametrally reversing.

Affiliated with

Also associated with

No associations

Rating

Diametral Pairs of Linear Extensions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Diametral Pairs of Linear Extensions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Diametral Pairs of Linear Extensions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-161743