A generalized-polymatroid approach to disjoint common independent sets in two matroids
A generalized-polymatroid approach to disjoint common independent sets in two matroids
复制标题
一种广义多拟阵方法，用于分离两个拟阵中不相交的公共独立集
DOI：
10.1016/j.disc.2019.03.009
复制
发表时间：
2019
影响因子：
0.8
通讯作者：
Kenjiro Takazawa and Yu Yokoi
中科院分区：
文献类型：
--
作者：
Yuni Iwamasa;Kenjiro Takazawa;Kenjiro Takazawa;Kenjiro Takazawa;Kenjiro Takazawa and Yu Yokoi
本文研究了基集E划分为k个公共独立集的问题的解存在的拟阵交类，其中E在两个拟阵中的每一个上都可以划分为k个独立集.对于这个问题，我们提出了一个新的方法，建立在广义多拟阵相交定理。我们展示，这种方法提供了替代的证明和统一的理解，以前的结果表明，该问题有一个解决方案的两个层状拟阵和两个拟阵没有（k+ 1）-跨越元素的交集。此外，我们新证明了一个层状拟阵和一个拟阵没有（k+ 1）-跨越元素的交集承认一个解决方案。我们还构造了一个例子的横向拟阵是不兼容的广义多拟阵的方法。
In this paper, we investigate the classes of matroid intersection admitting a solution for the problem of partitioning the ground set E into k common independent sets, where E can be partitioned into k independent sets in each of the two matroids. For this problem, we present a new approach building upon the generalized-polymatroid intersection theorem. We exhibit that this approach offers alternative proofs and unified understanding of previous results showing that the problem has a solution for the intersection of two laminar matroids and that of two matroids without (k+ 1)-spanned elements. Moreover, we newly show that the intersection of a laminar matroid and a matroid without (k+ 1)-spanned elements admits a solution. We also construct an example of a transversal matroid which is incompatible with the generalized-polymatroid approach.