论文标题
定向矩阵的旋塞图的直径：更新
Diameters of Cocircuit Graphs of Oriented Matroids: An Update
论文作者
论文摘要
定向的矩形（通常称为订单类型）是组合结构，可以概括点配置，向量配置，超平面布置，Polyhedra，线性程序和有向图。定向的矩形在组合学，计算几何形状和优化中发挥了关键作用。本文调查了先前的工作，并介绍了搜索定向矩阵的Cocircuit图的范围的搜索。 我们回顾了直径问题，并显示了一般定向的矩阵的直径界限，使其降低到定向矩阵的直径。我们为低级和低核心的定向矩阵提供了最新的精确界限，以及所有定向的矩阵，具有多达九个元素（此部分需要大型基于计算机的证明）。我们调查的动机是单纯形方法和纵横交错方法的复杂性。对于任意定向的矩阵，我们对Finschi的二次结构提出了改进。我们的讨论强调了与多元直径的多项式Hirsch猜想有关的两个非常重要的猜想。
Oriented matroids (often called order types) are combinatorial structures that generalize point configurations, vector configurations, hyperplane arrangements, polyhedra, linear programs, and directed graphs. Oriented matroids have played a key role in combinatorics, computational geometry, and optimization. This paper surveys prior work and presents an update on the search for bounds on the diameter of the cocircuit graph of an oriented matroid. We review the diameter problem and show the diameter bounds of general oriented matroids reduce to those of uniform oriented matroids. We give the latest exact bounds for oriented matroids of low rank and low corank, and for all oriented matroids with up to nine elements (this part required a large computer-based proof). The motivation for our investigations is the complexity of the simplex method and the criss-cross method. For arbitrary oriented matroids, we present an improvement to a quadratic bound of Finschi. Our discussion highlights two very important conjectures related to the polynomial Hirsch conjecture for polytope diameters.
