The Membership Problem in Jump Systems
The Membership Problem in Jump Systems
复制标题
跳转系统中的成员资格问题
DOI：
10.1006/jctb.1997.1744
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
L. Lovász
中科院分区：
文献类型：
--
作者：
L. Lovász
跳跃系统是满足特定交换公理的一组晶格点。这个概念是由Bouchet和Cunningham [2]引入的，作为（除其他）的常见概括（除其他）底座的集合集和图形子图的序列集。在其他假设下，我们证明了一个晶格点与跳跃系统的距离的最小最大公式。在上面的示例中满足了条件，因此我们的公式包含特殊情况，例如Tutte'SF-Factor Theorem和Edmonds的Matroid交点定理。
A jump system is a set of lattice points satisfying a certain exchange axiom. This notion was introduced by Bouchet and Cunningham [2], as a common generalization of (among others) the sets of bases of a matroid and degree sequences of subgraphs of a graph. We prove, under additional assumptions, a min-max formula for the distance of a lattice point from a jump system. The conditions are met in the examples above, and so our formula contains, as special cases, Tutte'sf-factor-theorem and Edmonds' matroid intersection theorem.