The d-Step Conjecture and Gaussian Elimination

The d-step conjecture is one of the fundamental open problems concerning the structure of convex polytopes. Let Δ (d,n) denote the maximum diameter of a graph of a d-polytope that has n facets. The d-step conjecture Δ (d,2d) = d is proved equivalent to the following statement: For each ``general position' real matrix M there are two matrices drawn from a finite group matrices isomorphic to the symmetric group on d letters, such that has the Gaussian elimination factorization L ^-1 U in which L and U are lower triangular and upper triangular matrices, respectively, that have positive nontriangular elements. If #(M) is the number of pairs giving a positive L ^-1 U factorization, then #(M) equals the number of d-step paths between two vertices of an associated Dantzig figure. One consequence is that #(M)≤ d!. Numerical experiments all satisfied #(M) ≥ 2 ^d-1 , including examples attaining equality for 3 ≤ d ≤ 15. The inequality #(M) ≥ 2 ^d-1 is proved for d=3. For d≥ 4, examples with #(M) =2 ^d-1 exhibit a large variety of combinatorial types of associated Dantzig figures. These experiments and other evidence suggest that the d-step conjecture may be true in all dimensions, in the strong form #(M) ≥ 2 ^d-1 . Received April 10, 1995, and in revised form August 23, 1995.