Theory and applications of freedom in matroids

To each cell e in a matroid M we can associate a non-negative integer ǁ e ǁ called the freedom of e. Geometrically the value ǁ e ǁ indicates how freely placed the cell is in the matroid. We see that ǁ e ǁ is equal to the degree of the modular cut generated by all the fully-dependent flats of M containing e. The relationship between freedom and basic matroid constructions, particularly one-point lifts and duality, is examined, and the applied to erections. We see that the number of times a matroid M can be erected is related to the degree of the modular cut generated by all the fully-dependent flats of M*. If ζ(M) is the set of integer polymatroids with underlying matroid structure M, then we show that for any cell e of M ǁ e ǁ= \frac{max\ f \ (e)}{f\in\zeta} We look at freedom in binary matroids and show that for a connected binary matroid M, ǁ e ǁ is the number of connected components of M/e. Finally the matroid join is examined and we are able to solve a conjecture of Lovasz and Recski that a connected binary matroid M is reducible if and only if there is a cell e of M with M/e disconnected.

Name dc:type.qualificationname

phd

Level dc:type.qualificationlevel

doctoral

Grantor dc:publisher.institution

The Open University

Year dc:date.issued

1981

Author dc:creator

• Duke, R.

Language dc:language

en