Hypergraphic matroid

From Egres Open
Jump to: navigation, search

Hypergraphic matroids were introduced by Lorea [1] as a generalization of graphic matroids. Given a hypergraph H=(V,E), a subset F of E is a hyperforest if one can choose two nodes from each hyperedge of F so that the resulting graph is a forest. The circuit matroid of H is the matroid on ground set E whose independent sets are the hyperforests. A matroid is hypergraphic if it is the circuit matroid of some hypergraph.

If M is the circuit matroid of a hypergraph H=(V,E), we call kM (the matroid sum of k copies of M) the k-circuit matroid of H. The k-circuit matroid has rank [math]k(|V|-1)[/math] if and only if H is k-partition-connected.


Although in many respect they are similar to graphic matroids, there are important differences:

  • Not all hypergraphic matroids are binary: If [math]|V|=3[/math] and E consists of 4 copies of V, we get [math]U_{4,2}[/math] as the circuit matroid.
  • The class of hypergraphic matroids is not closed under contraction.


  1. M. Lorea, Hypergraphes et matroides, Cahiers Centre Etud. Rech. Oper. 17 (1975), 289-291.