×

On the diameter of convex polytopes. (English) Zbl 0762.52004

Diese Arbeit gibt eine Abschätzung für den Durchmesser eines Polytops; damit wird ein Satz von Naddef verallgemeinert [D. Naddef, Math. Program., Ser. B 45, 109-110 (1989; Zbl 0684.90071)]. Die Untersuchungen verknüpfen sich mit der Arbeit von V. Klee und dem ersten Autor [Math. Oper. Res. 12, 718-755 (1987; Zbl 0632.52007)].
Die Verff. betrachten ein \(d\)-Polytop \(P\) im Raum \(\mathbb{R}^ n\), wo \(\dim(P)=d\) die affine Dimension bedeutet, und \(\text{vert}(P)\) die Eckpunktmenge von ihm bezeichnet. Die Symmetrisation von \(P\) ist mit \(P- P=\{x-y: x,y\in P\}\) bezeichnet, und sei \(k(P,w)=|\{\langle w,v\rangle: v\text{ vert}(P)\}|-1\). Der Durchmesser von \(P\) sei \(\delta(P)\), und \(\{w_ 1,w_ 2,\dots,w_ m\}\) ist eine Teilmenge von \(\mathbb{R}^ n\), deren lineare Spanne die Menge \(P-P\) enthält, ferner gelten die Ungleichungen \(k(P,w_ 1)\geq\cdots\geq k(P,w_ m)\), so besteht die Abschätzung: \[ \delta(P)\leq\sum^ d_{i=1}k(P,w_ i). \] {}.

MSC:

52B11 \(n\)-dimensional polytopes
51M16 Inequalities and extremum problems in real or complex geometry
Full Text: DOI

References:

[1] Brøndsted, A., An Introduction to Convex Polytopes (1983), Springer: Springer Berlin · Zbl 0509.52001
[2] Edmonds, J., Matroids and the greedy algorithm, Math. Prog., 1, 127-136 (1971) · Zbl 0253.90027
[3] Klee, V.; Kleinschmidt, P., The \(d\)-step conjecture and its relatives, Math. Oper. Res., 12, 718-755 (1987) · Zbl 0632.52007
[4] Naddef, D., The Hirsch conjecture is true for {0,1}-polytopes, Math. Prog., 45, 109-111 (1989) · Zbl 0684.90071
[5] Rado, R., Note on independence functions, Proc. London Math. Soc., 7, 300-320 (1957) · Zbl 0083.02302
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.