There are several clutters (antichains of sets) that can be associated with a matroid, as the clutter of circuits, the clutter of bases or the clutter of hyperplanes. We study the following question: given an arbitrary clutter $\Lambda$, which are the matroidal clutters that are closest to $\Lambda$? To answer it we first decide on the meaning of closest, and select one of the different matroidal clutters.
We show that for almost all reasonable choices above there is a finite set of matroidal clutters that approximate $\Lambda$ and, moreover, that $\Lambda$ can be recovered from them by a suitable operation. We also link our work to results in lattice theory, and give algorithmic procedures to compute the approximations. We are also interested in the same questions when we further require that both the original clutter and the matroidal approximations have the same ground set. In this situation, it is often the case that $\Lambda$ cannot be recovered by the approximating matroidal clutters (if they exist), but we can characterize when it does.
Although our initial interest was in matroids, our framework is general and applies in any situation when one wishes to decompose the clutter $\Lambda$ with members of a favourite family of clutters, not necessarily a matroidal one.
(Joint work with Jaume Martí-Farré and José Luis Ruiz.)
[-]
There are several clutters (antichains of sets) that can be associated with a matroid, as the clutter of circuits, the clutter of bases or the clutter of hyperplanes. We study the following question: given an arbitrary clutter $\Lambda$, which are the matroidal clutters that are closest to $\Lambda$? To answer it we first decide on the meaning of closest, and select one of the different matroidal clutters.
We show that for almost all reasonable ...
[+]