On the notion of generalized minor in topological network theory and matroids

• Published in: Linear algebra and its applications 2014-10, Vol.458, p.1-46
• Main Authors: Theja, Siva, Narayanan, H.
• Format: Article
• Language: English
• Subjects: Generalized minors; Implicit duality; Matroids; Polymatroids
• ISSN: 0024-3795; 1873-1856
• DOI: 10.1016/j.laa.2014.06.008

In this paper we consider a linking operation between matroids, defined as MSP↔MS=(MSP∨MS)×P, where MSP and MS are matroids on sets S∪P and S respectively. This operation can be seen as a generalization of the minor operations on matroids, in the sense that we can speak of a minor of a matroid on S∪P relative to another matroid on S. This is analogous to a similar idea for vector spaces which is useful in topological network theory. We show some interesting properties for this linking operation. These include (1) an implicit duality theorem, which says that the dual of the generalized minor of MSP relative to MS is same as the generalized minor of MSP⁎ relative to MS⁎, (2) attaching two matroids along a common independent set such that the resulting matroid contains the two matroids as restrictions, (3) a topological transformation result, where given two matroids on the same underlying set, we build a matroid on a bigger set such that the two matroids can be obtained as minors of the larger matroid. Analogy between topological network theory and matroids leads us to a construction of self-dual matroids starting from smaller and simpler self-dual matroids. We use the implicit duality result to show that if MSP and MS are self-duals, then MSP↔MS is also a self-dual matroid. Finally we show that this linking idea can be directly extended to polymatroid rank functions.