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.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.