On the number of common bases of two matroids
type: Item
instance of: scholarly article
title: On the number of common bases of two matroids
zbMATH Open document ID: 0541.05018
DOI: 10.1016/0012-365X(83)90038-9
author: A. Zemirline
author: Jean Fonlupt
published in: Discrete Mathematics
publication date: 1983-01-01T00:00:00Z
review text: Let \(M_ i=(E,F_ i)\), \(i=1,2\), be two simple matroids on the same finite set E \((F_ i\) being the family of independent sets for \(M_ i)\). By studying the dimension of the intersection of the polytope \(K(M_ i)\) representing \(M_ i\), \(i=1,2\), (that is, \(K(M_ i)\) is the polytope having as extreme points the representative vectors of the bases of \(M_ i)\), the authors obtain \(| E| -(d_ 1+d_ 2)+2\) for the least number of common bases of \(M_ 1\) and \(M_ 2\), assuming there exists at least one basis in common, where \(d_ i\) is the index of decomposition of \(M_ i\). A number of interesting applications to graph theory are given.
Mathematics Subject Classification ID: 05B35
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 3859142
zbMATH Keywords: bases
zbMATH Keywords: bipartite matching
zbMATH Keywords: directed spanning trees
zbMATH Keywords: index of decomposition
MaRDI profile type: Publication
cites work: Matroids and the greedy algorithm
cites work: Q5684698
cites work: Q3048571
cites work: State Constraints in Convex Control Problems of Bolza
cites work: Q4111952
full work available at URL: 0012-365x(83)90038-9
OpenAlex ID: W2070835108
description: scientific article; zbMATH DE number 3859142