Equicovering matroids by distinct bases (Q1891366)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Equicovering matroids by distinct bases |
scientific article; zbMATH DE number 759654
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Equicovering matroids by distinct bases |
scientific article; zbMATH DE number 759654 |
Statements
Equicovering matroids by distinct bases (English)
0 references
28 September 1995
0 references
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.
0 references
matroid
0 references
distinct bases
0 references
cyclic order conjecture
0 references
0 references
0.9003524
0 references
0.8989023
0 references
0.89512014
0 references
0.89512014
0 references
0.8941056
0 references
0.89171743
0 references
0 references
0.8908668
0 references