A critical look at the definition of multidimensional separations

Multidimensional (MD) separations, especially comprehensive two-dimensional (2D) separations such as comprehensive 2D LC (LC × LC), and comprehensive 2D GC (GC × GC), are potentially powerful separation techniques. It is important to have a clear definition of MD techniques to better understand the scope and boundaries of the subject. Widely accepted definitions of MD Separations have their roots in the definition proposed by Giddings. Giddings also added several comments that clarified the scope of his definition. However, some researchers extend Giddings’ definitions beyond their intended scope. Doing so disqualifies such comprehensive 2D techniques as LC × LC, GC × GC and 2D TLC from being considered as 2D techniques. In other instances, extended treatment of Giddings’ definition is used as a basis to justify design-parameters of comprehensive 2D separations despite the fact that these parameters lead to sub-optimal implementations. We believe that the shortcomings in the definition and its popular interpretations are serious enough to warrant attention, especially by those interested in designing optimal instrumentation for MD separations like comprehensive 2D GC. After discussion of the weaknesses in the currently used definitions, we propose to define n-dimensional analysis as one that generates n-dimensional displacement information. We believe that this definition captures the spirit of Giddings’ definition while avoiding the problems associated with its popular interpretations.     

Combinatorial Markov chains on linear extensions

We consider generalizations of Schützenberger’s promotion operator on the set $\mathcal{L}$ of linear extensions of a finite poset of size n. This gives rise to a strongly connected graph on $\mathcal{L}$ . By assigning weights to the edges of the graph in two different ways, we study two Markov chains, both of which are irreducible. The stationary state of one gives rise to the uniform distribution, whereas the weights of the stationary state of the other have a nice product formula. This generalizes results by Hendricks on the Tsetlin library, which corresponds to the case when the poset is the anti-chain and hence $\mathcal{L}=S_{n}$ is the full symmetric group. We also provide explicit eigenvalues of the transition matrix in general when the poset is a rooted forest. This is shown by proving that the associated monoid is $\mathcal {R}$ -trivial and then using Steinberg’s extension of Brown’s theory for Markov chains on left regular bands to $\mathcal {R}$ -trivial monoids.     

Many Polytopes Meeting the Conjectured Hirsch Bound

The still open Hirsch conjecture asserts that Δ(d,n) ≤n-d for all n > d ≥ 2 , where Δ (d,n) denotes the maximum edge-diameter of (convex) d -polytopes with n facets. This paper adds to the list of pairs (d,n) that are known to be H -sharp in the sense that Δ (d,n) ≥ n-d . In particular, it is proved that Δ(d,n)≥ n-d for all n > d ≥ 14 . Received November 20, 1996, and in revised form March 21, 1997.     

Linear algorithms for testing the sign stability of a matrix and for findingZ-maximum matchings in acyclic graphs

Summary Ann×n real matrixA=(a _ij ) isstable if each eigenvalue has negative real part, andsign stable (orqualitatively stable) if each matrix B with the same sign-pattern asA is stable, regardless of the magnitudes ofB's entries. Sign stability is of special interest whenA is associated with certain models from ecology or economics in which the actual magnitudes of thea _ij may be very difficult to determine. Using a characterization due to Quirk and Ruppert, and to Jeffries, an efficient algorithm is developed for testing the sign stability ofA. Its time-and-space-complexity are both 0(n ²), and whenA is properly presented that is reduced to 0(max{n, number of nonzero entries ofA}). Part of the algorithm involves maximum matchings, and that subject is treated for its own sake in two final sections.