The Hirsch conjecture holds for normal flag complexes

Autor:	Adiprasito, Karim Alexander, Benedetti, Bruno
Rok vydání:	2013
Předmět:	Mathematics - Combinatorics Mathematics - Metric Geometry Mathematics - Optimization and Control 05C12 90C05 05E45 52B70 53C21
Druh dokumentu:	Working Paper
Popis:	Using an intuition from metric geometry, we prove that any flag and normal simplicial complex satisfies the non-revisiting path conjecture. As a consequence, the diameter of its facet-ridge graph is smaller than the number of vertices minus the dimension, as in the Hirsch conjecture. This proves the Hirsch conjecture for all flag polytopes, and more generally, for all (connected) flag homology manifolds. Comment: 9 pages, 1 figure; to appear in Mathematics of Operations Research
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1303.3598 Zobrazit plný text záznamu View this record from Arxiv