Name
Abstract | ||
|---|---|---|
The d-step conjecture is one of the fundamental open problems concerning the structure of convex polytopes. Let Delta(d, n) denote the maximum diameter of a graph of a d-polytope that has n facets. The d-step conjecture a(d, 2d) = d is proved equivalent to the following statement: For each ''general position'' (d - 1) x (d - 1) real matrix M there are two matrices Q(tau), Q(sigma) drawn from a finite group (S) over cap(d) of (d - 1) x (d - 1) matrices isomorphic to the symmetric group Sym(d) on d letters, such that Q(tau) M Q(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) is an element of Sym(d) x Sym(d) giving a positive L-1 U factorization. then #(hl) equals the number of d-step paths between two vertices of an associated Dantzig figure. One consequence is that #(M) less than or equal to d!. Numerical experiments all satisfied #(M) greater than or equal to 2(d-1),including examples attaining equality for 3 less than or equal to d less than or equal to 15. The inequality rf(M) greater than or equal to 2(d-1) is proved for d = 3, For d greater than or equal to 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) greater than or equal to 2(d-1). |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1007/PL00009308 | DISCRETE & COMPUTATIONAL GEOMETRY |
Keywords | DocType | Volume |
convex polytope,symmetric group,gaussian elimination,satisfiability | Journal | 18 |
Issue | ISSN | Citations |
1 | 0179-5376 | 4 |
PageRank | References | Authors |
1.54 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| J. C. Lagarias | 1 | 563 | 235.61 |
| Nagabhushana Prabhu | 2 | 22 | 7.43 |
| James A. Reeds | 3 | 864 | 84.20 |