Monotone paths on polytopes

Christos A. Athanasiadis, Paul H. Edelman, Victor Reiner

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

We investigate the vertex-connectivity of the graph of f-monotone paths on a d-polytope P with respect to a generic functional f. The third author has conjectured that this graph is always (d - 1)-connected. We resolve this conjecture positively for simple polytopes and show that the graph is 2-connected for any d-polytope with d ≥ 3. However, we disprove the conjecture in general by exhibiting counterexamples for each d ≥ 4 in which the graph has a vertex of degree two. We also re-examine the Baues problem for cellular strings on polytopes, solved by Billera, Kapranov and Sturmfels. Our analysis shows that their positive result is a direct consequence of shellability of polytopes and is therefore less related to convexity than is at first apparent.

Original languageEnglish (US)
Pages (from-to)315-334
Number of pages20
JournalMathematische Zeitschrift
Volume235
Issue number2
DOIs
StatePublished - Oct 2000

Fingerprint Dive into the research topics of 'Monotone paths on polytopes'. Together they form a unique fingerprint.

Cite this