An Elementary Approach to the Principal Partition of a Matroid

Harihar NARAYANAN  Manohar Narhar VARTAK  

IEICE TRANSACTIONS (1976-1990)   Vol.E64   No.4   pp.227-234
Publication Date: 1981/04/25
Online ISSN: 
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Mathematics

Full Text: PDF(657.9KB)
>>Buy this Article

This paper deals with an elementary alternative approach to the notion of the principal partition of a matroid into strongly irreducible minors. This approach makes use of the matroid union theorem and the concept of the density of a matroid introduced in this paper. For a matroid M on S the density d(M)S/r(M). The principal partition of a matroid M on S is constructed by first constructing a partition of S called the P-sequence of M. On the resulting sub-sets irreducible minors are constructed. An irreducible minor is further partitioned into strongly irreducible minors by examining all its restrictions of density equal to its own. It is constructively shown that the P-sequence of a matroid M can be obtained by considering the intersections of sets of coloops of matroids obtained from M by repeated use of the matroid union () and the dualization (*) operator. It is shown that the principal partition for such matroids can be immediately constructed if the principal partition for the original matroid were given. Finally, efficient algorithms are outlined for constructing the principal partition.