Posets Arising as 1-Skeleta of Simple Polytopes, the Nonrevisiting Path Conjecture, and Poset Topology
Posets Arising as 1-Skeleta of Simple Polytopes, the Nonrevisiting Path Conjecture, and Poset Topology
复制标题
作为简单多面体的 1-骨架产生的偏序集、不重访路径猜想和偏序集拓扑
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
P. Hersh
中科院分区：
文献类型：
--
作者：
P. Hersh
给定任意多面体$P$和任意一般线性泛函${fc}$，取$P$的1-骨架，将${fc}(U)<；{fc}(V)$的每条边$e(u，v)$从$u$定向到$v$，从而得到有向图$G(P，{fc})$。本文研究了关于多面体$P$和一般代价向量$f{c}$的充分条件，使得图$G(P，{fc})$在离开$P$后不会有任何重访$P$面的有向路.这相当于在$P$和${f c}$上寻找条件的问题，在这些条件下，线性规划的单纯形法在所有枢轴规则的选择下都是有效的。给出了可证明地产生期望有向图面不可重访性质的推论的条件，并且该条件可能足以给出期望性质本身。提出的条件之一是$G(P，{fc})$是偏序集的Hasse图，这等价于要求不需要重访一维面。这为偏序集理论技术的使用打开了大门。
这也得到了单多面体的一个结果，其中$G(P，{fc})$是格$L$的哈斯图，$L$中每个开区间的序复形是同伦的等价于一个球或某一维的球面.应用于弱Bruhat序、Tamari格，以及更一般的寒武纪格子，使用这些偏序集的Hasse图的实现作为置换面体、缔合面体和广义缔合面体的1-骨架。
Given any polytope $P$ and any generic linear functional ${f c} $, one obtains a directed graph $G(P,{f c})$ by taking the 1-skeleton of $P$ and orienting each edge $e(u,v)$ from $u$ to $v$ for ${f c} (u) <{f c} ( v)$. This paper examines the question of finding sufficient conditions on a polytope $P$ and generic cost vector $f{ c}$ so that the graph $G(P, {f c} )$ will not have any directed paths which revisit a face of $P$ after departing from it. This is equivalent to the question of finding conditions on $P$ and ${f c} $ under which the simplex method for linear programming will be efficient under all choices of pivot rules. Conditions are given which provably yield a corollary of the desired directed graph face nonrevisiting property and which could perhaps suffice to give the desired property itself. One of the conditions proposed is that $G(P,{f c} )$ be the Hasse diagram of a partially ordered set, which is equivalent to requiring nonrevisiting of 1-dimensional faces. This opens the door to the usage of poset-theoretic techniques.
This also leads to a result for simple polytopes in which $G(P,{f c})$ is the Hasse diagram of a lattice $L$ that the order complex of each open interval in $L$ is homotopy equivalent to a ball or a sphere of some dimension. Applications are given to the weak Bruhat order, the Tamari lattice, and more generally to the Cambrian lattices, using realizations of the Hasse diagrams of these posets as 1-skeleta of permutahedra, associahedra, and generalized associahedra.