Adjacency, Inseparability, and Base Orderability in Matroids

详细信息	查看全文 | 推荐本文 |

• 作者：Keijsper ; J. ; Pendavingh ; R. ; Schrijver ; A.
• 刊名：European Journal of Combinatorics
• 出版年：2000
• 期刊代码：65_01956698
• 类别：mt
• 出版时间：May, 2000
• 卷：21
• 期：4
• 页码：487-502
• 文件大小：169 K

摘要

Two elements in an oriented matroid are inseparable if they have either the same sign in every signed circuit containing them both or opposite signs in every signed circuit containing them both. Two elements of a matroid are adjacent if there is no M(Kb>4b>)-minor using them both, and in which they correspond to a matching ofKb>4b> . We prove that two elements e, f of an oriented matroid are inseparable if and only ife, f are inseparable in every M(Kb>4b>) orUb>4b>² -minor containing them. This provides a link between inseparability in oriented matroids (introduced by Bland and Las Vergnas) and adjacency in binary matroids (introduced by Seymour). We define the concepts of base orderable and strongly base orderable subsets of a matroid, generalizing the definitions of base orderable and strongly base orderable matroids. Strongly base orderable subsets can be used to obtain packing and covering results, generalizing results of Davies and McDiarmid, as was shown in a previous paper. In this paper, we prove that any pairwise inseparable subset of an oriented matroid is base orderable. For binary matroids we derive the following characterization: a subset is strongly base orderable if and only if it is pairwise adjacent.