From Clutters to Matroids

  • Jaume Martí-Farré
Keywords: Clutter, Hypergraph, Matroid, Circuits.


This paper deals with the question of completing a monotone increasing family of subsets $\Gamma$ of a finite set $\Omega$ to obtain the dependent sets of a matroid. Specifically, we provide several natural processes for transforming the clutter $\Lambda$ of the inclusion-minimal subsets of the family $\Gamma$ into the set of circuits ${\cal C}({\cal M})$ of a matroid ${\cal M}$ with ground set $\Omega$. In addition, by combining these processes, we prove that all the minimal matroidal completions of the family can be obtained.

Article Number