ISSN:
1432-0444
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. 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'' $(d-1)\times (d-1)$ real matrix M there are two matrices $Q_{\tau}, Q_{\sigma}$ drawn from a finite group $\hat{S}_d$ of $(d-1)\times (d-1)$ matrices isomorphic to the symmetric group $\mathop{\rm Sym}\nolimits (d)$ on d letters, such that $Q_{\tau} MQ_{\sigma}$ 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 $(\sigma,\tau) \in \mathop{\rm Sym}\nolimits(d) \times \mathop{\rm Sym}\nolimits (d)$ 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 .
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/PL00009308
Permalink
