Equicovering matroids by distinct bases
type: Item
instance of: scholarly article
title: Equicovering matroids by distinct bases
zbMATH Open document ID: 0822.05015
DOI: 10.1016/0195-6698(95)90055-1
author: Pierre Fraisse
author: Pavol Hell
published in: European Journal of Combinatorics
publication date: 1995-09-28T00:00:00Z
review text: Let \(M\) be a matroid on the set \(E\) of \(m\) elements and suppose that the rank \(r(E)\) divides \(m\). Then \(E\) can be partitioned into distinct bases iff \(| X|/ r(X)\leq m/r(E)\) holds for all \(X\subseteq E\). The cyclic order conjecture (see \textit{Y. Kajitani}, \textit{S. Ueno} and \textit{H. Miyano} [Discrete Math. 72, No. 1-3, 187-194 (1988; Zbl 0657.05018)]) states that in this case the elements of \(E\) can be cyclically ordered so that any \(r(E)\) consecutive elements \((\text{mod } m)\) form a base of \(M\). The authors prove that if \(k\leq r(M)< m\) or if \(k= 1\) and \(r(M)= m\) then a necessary and sufficient condition for the existence of \(p\) distinct bases of \(M\) so that each element of \(E\) is covered exactly \(k\) times is that the above inequality and \(k\cdot m= p\cdot r(M)\) hold. This is weaker than the conjecture (put \(p= m\), \(k= r(E)\)) but may be useful for its proof.
reviewed by: András Recski
Mathematics Subject Classification ID: 05B35
Mathematics Subject Classification ID: 05B40
zbMATH DE Number: 759654
zbMATH Keywords: matroid
zbMATH Keywords: distinct bases
zbMATH Keywords: cyclic order conjecture
MaRDI profile type: Publication
full work available at URL: 0195-6698(95)90055-1
OpenAlex ID: W2085852602
cites work: Combinatorial theory.
cites work: Lehmans switching game and a theorem of Tutte and Nash-Williams
cites work: Equiarboreal graphs
cites work: Q3328583
cites work: Q5184928
cites work: Ordering of the elements of a matroid such that its consecutive w elements are independent
cites work: Q5582910
Recommended article: On the number of bases of almost all matroids
Recommended article: Q3835465
Recommended article: Counting bases of representable matroids
Recommended article: Bounding the number of bases of a matroid
Recommended article: Bases-cobases graphs and polytopes of matroids
Recommended article: Q4543335
Recommended article: Matroid bases with cardinality constraints on the intersection
Recommended article: On some properties of base-matroids
Recommended article: A few theorems concerning pairs of matroid bases
description: scientific article; zbMATH DE number 759654