Monotone paths on polytopes

Citation
Ca. Athanasiadis et al., Monotone paths on polytopes, MATH Z, 235(2), 2000, pp. 315-334
Citations number
17
Categorie Soggetti
Mathematics
Journal title
MATHEMATISCHE ZEITSCHRIFT
ISSN journal
00255874 → ACNP
Volume
235
Issue
2
Year of publication
2000
Pages
315 - 334
Database
ISI
SICI code
0025-5874(200010)235:2<315:MPOP>2.0.ZU;2-X
Abstract
We investigate the vertex-connectivity of the graph of f-monotone paths on a cl-polytope P with respect to a generic functional f. The third author ha s conjectured that this graph is always (d - 1)-connected. We resolve this conjecture positively for simple polytopes and show that the graph is 2-con nected for any d-polytope with d greater than or equal to 3. However,we dis prove the conjecture in general by exhibiting counterexamples for each d gr eater than or equal to 4 in which the graph has a vertex of degree two. We also re-examine the Baues problem for cellular strings on polytopes, sol ved by Billera, Kapranov and Sturmfels. Our analysis shows that their posit ive result is a direct consequence of shellability of polytopes and is ther efore less related to convexity than is at first apparent.