论文标题
Matroid相交等级的下限
A Lower Bound for the Rank of Matroid Intersection
论文作者
论文摘要
Matroid是组合数学中许多基本对象的概括，而Matroid相交问题是组合优化的经典主题。但是，只有两个矩形的交集才能得到充分理解。交叉问题的解决方案超过三个矩形被证明是\ textbf {np-hard}。我们将对Matroid相交中常见独立集的最大基数进行下限估计。我们还将研究两个以上的矩形的交点的某些特性，并推断出Edmonds的Min-Max定理用于Matroids交点的一些类似结果。
Matroid is a generalization of many fundamental objects in combinatorial mathematics , and matroid intersection problem is a classical subject in combinatorial optimization . However , only the intersection of two matroids are well understood . The solution of the intersection problem of more than three matroids is proved to be \textbf{NP-hard} . We will give a lower bound estimate on the maximal cardinality of the common independent sets in matroid intersections . We will also study some properties of the intersection of more than two matroids and deduce some analogous results for Edmonds' Min-max theorems for matroids intersection .
