Algorithms for computing lengths of chains in integral partition lattices
Let P-1,P-n denote the partition lattice of 1 with n parts, ordered by Hardy-Littlewood-Polya majorization. For any two comparable elements x and y of P-1,P-n we denote by M(x, y), m(x, y), f(x, y), and F(x, y), respectively, the sizes of four typical chains between x and y: the longest chain, the shortest chain, the lexicographic chain, and the counter-lexicographic chain. The covers u=(u(1),...,u(n)) > v=(v(1),...,v(n)) in P-1,P-n are of two types: N-shift (nearby shift) where v(i)=u(i) - 1, v(i)+1 = u(i+1) + 1 for some i; and D-shift (distant shift) where u(i) - 1 = v(i) = v(i+1) = ... = v(j) = u(j) + 1 for some i and j. An N-shift (a D-shift) is pure if it is not a D-shift (an N-shift). We develop linear algorithms for calculating M(x, y), m(x, y), f (x, y), and F(x, y), using the leftmost pure N-shift first search, the rightmost pure D-shift first search, the leftmost N-shift first search, and the rightmost D-shift first search, respectively. Those algorithms have significant applications in complexity analysis of biological sequences. (C) 2002 Elsevier Science B.V. All rights reserved.
algorithm length chain partition lattice majorization nearby shift distant shift