The brick polytope of a sorting network
The brick polytope of a sorting network
复制标题
排序网络的砖多面体
DOI：
10.1016/j.ejc.2011.12.003
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
F. Santos
中科院分区：
文献类型：
--
作者：
Vincent Pilaud;F. Santos
关联面体是一个多面体，其图是凸多边形的三角剖分上的翻转图。伪三角剖分和多重三角剖分以两种不同的方式推广三角剖分，Pilaud和Pocchiola在研究具有给定排序网络支持的联系人的伪线排列上的翻转图时统一了这两种方法。在这篇文章中，我们构造了排序网络的砖多面体，得到了与该网络所支持的每个伪线排列相关联的砖向量的凸壳。我们组合刻画了这个多面体的顶点，描述了它的面，并将它分解为拟阵多面体的Minkowski和。我们的砖多面体包括Hohlweg&Lange对关联体的许多实现，它们作为砖多面体出现在某些精心选择的排序网络中。此外，我们还讨论了支持伪线排列的排序网络的砖多面体，它们对应于凸多边形的多三角剖分：我们的多面体只实现了多三角剖分上的翻转图的子图，它们不能表现为假设的多结合面体的投影。
The associahedron is a polytope whose graph is the graph of flips on triangulations of a convex polygon. Pseudotriangulations and multitriangulations generalize triangulations in two different ways, which have been unified by Pilaud & Pocchiola in their study of flip graphs on pseudoline arrangements with contacts supported by a given sorting network. In this paper, we construct the brick polytope of a sorting network, obtained as the convex hull of the brick vectors associated to each pseudoline arrangement supported by the network. We combinatorially characterize the vertices of this polytope, describe its faces, and decompose it as a Minkowski sum of matroid polytopes. Our brick polytopes include Hohlweg & Lange’s many realizations of the associahedron, which arise as brick polytopes for certain well-chosen sorting networks. We furthermore discuss the brick polytopes of sorting networks supporting pseudoline arrangements which correspond to multitriangulations of convex polygons: our polytopes only realize subgraphs of the flip graphs on multitriangulations and they cannot appear as projections of a hypothetical multiassociahedron.
子词复合体、簇复合体和广义多关联面体
影响因子：
0.8
作者：
Cesar Ceballos;Jean-Philippe Labbé;Christian Stump
通讯作者：
Christian Stump