论文标题
分裂矩阵中基对的交换距离
Exchange distance of basis pairs in split matroids
论文作者
论文摘要
基础交换公理一直是Matroid理论发展的推动力。但是，公理仅给出了基础关系的局部特征，这是进一步进步的主要绊脚石，并且对矩阵基础的结构进行全球理解是矩阵优化的基本目标。 在研究对称交换的结构时，Gabow提出了一个问题，即任何一对碱都可以接受一系列对称交换。怀特提出了交换公理的不同扩展，他们研究了兼容基序列的等效性。这些猜想表明，矩形基地的家族具有比我们所知道的要强得多的结构特性。 在本文中，我们根据对称交换来研究矩阵的基对的距离。特别是，我们给出了一种多项式时间算法，该算法决定了最短的交换序列，该算法将基型对转化为另一个用于分裂的矩阵，该类别是由从热带几何学角度研究的矩阵多型研究激励的。作为推论，我们验证了上述大型阶级的长期猜想。作为分裂矩形的子类，我们的结果也解决了铺路矩阵的猜想。
The basis exchange axiom has been a driving force in the development of matroid theory. However, the axiom gives only a local characterization of the relation of bases, which is a major stumbling block to further progress, and providing a global understanding of the structure of matroid bases is a fundamental goal in matroid optimization. While studying the structure of symmetric exchanges, Gabow proposed the problem that any pair of bases admits a sequence of symmetric exchanges. A different extension of the exchange axiom was proposed by White, who investigated the equivalence of compatible basis sequences. These conjectures suggest that the family of bases of a matroid possesses much stronger structural properties than we are aware of. In the present paper, we study the distance of basis pairs of a matroid in terms of symmetric exchanges. In particular, we give a polynomial-time algorithm that determines a shortest possible exchange sequence that transforms a basis pair into another for split matroids, a class that was motivated by the study of matroid polytopes from a tropical geometry point of view. As a corollary, we verify the above mentioned long-standing conjectures for this large class. Being a subclass of split matroids, our result settles the conjectures for paving matroids as well.
