Theory and applications of freedom in matroids

Duke, R. (1981). Theory and applications of freedom in matroids. PhD thesis The Open University.

DOI: https://doi.org/10.21954/ou.ro.0000de47

Abstract

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.

Viewing alternatives

Look up in Google Scholar

Download history

Metrics

Public Attention

Altmetrics from Altmetric

Number of Citations

Citations from Dimensions

Item Actions

Export

About

CORE (COnnecting REpositories)

Recommendations