In some of my recent work, I have 'discovered' a binary matroid which I will describe below.

Given a graph $G$, let $H_1(G, \mathbb{Z}/2\mathbb{Z})$ denote the cycle space. This is a vector space over $\mathbb{Z}/2\mathbb{Z}$. Moreover, every cycle of $G$ corresponds to a vector in $H_2(G, \mathbb{Z}/2\mathbb{Z})$. Let $M(G)$ denote the matroid whose elements are the cycles of $G$. Here, the rank of a set of cycles is the rank of the corresponding set of vectors.

Equivalently, given a graph $G$ and a subset $S$ of cycles is independent if there is an edge of the graph which appears in an odd number of the cycles in $S$.

This matroid clearly has been studied before. However, I have been unable to answer the following question: 1) What is the name of this matroid?

Since it is related to the set of cycles of a graph, it is hard to find papers on it. The best I have found come from papers in complexity theory studying minimum weight cycle bases, or from homework exercises. However, I have not found a paper that decides to give this class of matroids a name.


You can build such a matroid from the circuits of another binary, or representable in general, matroid as well. Some papers make use of such structure, either regarded as a chain group or simply as a subset of a vector space. But to the best of my knowledge I don't think there is a name for such matroids.

  • 1
    $\begingroup$ Can you give references for a few of the papers that use this structure? $\endgroup$
    – j.c.
    Jan 23 '19 at 18:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.