Equicovering matroids by distinct bases (Q1891366): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: Q790131 / rank | |||
Property / author | |||
Property / author: Pavol Hell / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0195-6698(95)90055-1 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2085852602 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Combinatorial theory. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Lehmans switching game and a theorem of Tutte and Nash-Williams / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Equiarboreal graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3328583 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5184928 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Ordering of the elements of a matroid such that its consecutive w elements are independent / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5582910 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 14:42, 23 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Equicovering matroids by distinct bases |
scientific article |
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