Record Details

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

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title On the notion of generalized minor in topological network theory and matroids
 
Creator THEJA, S
NARAYANAN, H
 
Subject Matroids
Generalized minors
Implicit duality
Polymatroids
DECOMPOSITION
PARTITION
SYSTEMS
 
Description In this paper we consider a linking operation between matroids, defined as M-SP M-S= (M-SP V M-S) X P, where M-SP and Ms are matroids on sets S UP 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 U 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 M-SP relative to Ms is same as the generalized minor of M*,sp relative to M, (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 M-SP and Ms are self-duals, then M-SP M-S Ms is also a self-dual matroid. Finally we show that this linking idea can be directly extended to polymatroid rank functions. (C) 2014 Elsevier Inc. All rights reserved.
 
Publisher ELSEVIER SCIENCE INC
 
Date 2014-12-28T16:25:41Z
2014-12-28T16:25:41Z
2014
 
Type Article
 
Identifier LINEAR ALGEBRA AND ITS APPLICATIONS, 4581-46
0024-3795
1873-1856
http://dx.doi.org/10.1016/j.laa.2014.06.008
http://dspace.library.iitb.ac.in/jspui/handle/100/16879
 
Language English