Abstract
In this note we prove a theorem on the diameter of convex polytopes, which generalizes a theorem of Naddef 4]. For a recent survey on diameters of polytopes and the related d-step conjecture, the reader can consult 3].
Abstract
For a polytope P in IR n , we denote by dim(P) its a ne dimension, by vert(P) its vertex set, by d P (u; v) the distance between two vertices on its 1-skeleton, and by (P ) its diameter.
Abstract
The symmetrization of P is denoted by P ? P = fx ? y : x; y 2 Pg. The linear span of a subset S of IR n is denoted by lin(S), and the orthogonal complement of a subspace L by L ? . For a linear functional w on IR n , denote by k(P; w) the number of distinct values attained by the vertices of P under w, minus one, i.e. k(P; w) = jfhw; vi : v 2 vert(P)gj ? 1, and by F ? (P; w) and F + (P; w) denote the faces of P containing those vertices attaining the minimum and maximum values under w, respectively. Theorem Let P be a d-polytope in IR n , let fw 1 ; w m g be a subset of IR n whose linear span contains P ? P, and assume k(P; w 1 ) k(P; w m ). Then (P ) P d i=1 k(P; w i ):
Abstract
Proof. By induction on d = dim(P). The bound trivially holds for d = 0. Assume then, that d 1 and the bound is valid for all dimensions smaller than d. Now, P ? P L = lin(fw 1 ; ; w m g) implies P ? P 6 L ? = \ m i=1 w ?

In this note we prove a theorem on the diameter of convex polytopes, which generalizes a theorem of Naddef 4] . For a recent survey on diameters of polytopes and the related d-step conjecture, the reader can consult 3].

For a polytope P in IR n , we denote by dim(P) its a ne dimension, by vert(P) its vertex set, by d P (u; v) the distance between two vertices on its 1-skeleton, and by (P ) its diameter.

The symmetrization of P is denoted by P ? P = fx ? y : x; y 2 Pg. The linear span of a subset S of IR n is denoted by lin(S), and the orthogonal complement of a subspace L by L ? . For a linear functional w on IR n , denote by k(P; w) the number of distinct values attained by the vertices of P under w, minus one, i.e. k(P; w) = jfhw; vi : v 2 vert(P)gj ? 1, and by F ? (P; w) and F + (P; w) denote the faces of P containing those vertices attaining the minimum and maximum values under w, respectively. Theorem Let P be a d-polytope in IR n , let fw 1 ; w m g be a subset of IR n whose linear span contains P ? P, and assume k(P; w 1 ) k(P; w m ). Then (P ) P d i=1 k(P; w i ): 

which completes the proof.

Applying the theorem with the standard basis fe 1 ; ; e n g of IR n , we obtain the following bound on the diameter of an integer polytope.

Corollary If V f0; 1; ; kg n then (conv(V )) k dim(conv(V )):

Finally, we re ne the theorem as follows. Let P be a d-polytope in IR n where, to simplify notation, we assume d 1, and let fw 1 ; ; w m g be a subset of IR n whose linear span contains L = lin(P ? P). Assume that k(P; w 1 ) k(P; w m ) (the reverse of the order assumed in the theorem). For i = 1; ; m let u i be the orthogonal projection of w i onto L, so k(P; u i ) = k(P; w i ), and let U = fu 1 ; ; u m g, so L = lin(U). Applying the theorem with any basis of U, i.e. a subset fu i 1 ; ; u i d g of U which is a basis of L, an upper bound (P ) P d j=1 k(P; u i j ) is obtained.

Appealing to the well known validity of the so-called greedy algorithm for nding a minimal weight basis of a matroid ( 5] , 2]), we nd that the basis of U yielding the best upper bound is the lexicographically rst one, i.e. the basis fu i 1 ; ; u i d g, where i 1 < < i d and, for j = 1; ; d, the index i j is the smallest such that u i j is nonzero and is not contained in lin(fu ir : r < jg).

We thus have the following re ned version of the theorem.

Theorem Let P be a d-polytope in IR n where d 1, let fw 1 ; w m g be a subset of IR n whose linear span contains P ? P, and assume k(P; w 1 ) k(P; w m ). For i = 1; ; m, let u i be the orthogonal projection of w i onto lin(P ? P), and let fu i 1 ; ; u i d g be the lexicographically rst basis of fu 1 ; ; u m g. Then (P ) P d j=1 k(P; w i j ):

{'paper_id': '5997490', 'title': 'On the diameter of convex polytopes', 's2_url': 'https://api.semanticscholar.org/CorpusID:5997490', 'source': 'S2ORC'}