1
$\begingroup$

I found the following definition in an introductory exposition about matroids.

Let $G=(V,E)$ be a given (finite) graph. Let $\mathcal{C, D}$ be arbitrary collections of cycles in $G$.

$\mathcal{C}$ is redundant, if every edge in $G$ appears in an even number of cycles of $\mathcal{C}$. $\mathcal{D}$ is independent, if there is no subset of $\mathcal{D}$ which is redundant.

I am supposed to be showing that the set of independent sets of cycles form a matroid.

I do not know how to proceed here, or what this notion of redundancy is actually referring to. It took me a while to come up with a graph and a redundant cycle set, but I didn't get any intuition of what this is about.

What is the intuition behind these objects? How do I proceed to show that these indeed form a matroid?

$\endgroup$
4
$\begingroup$

Think of a cycle (or in general any subgraph of $G$) as an element of $\mathbb F_2^{|E|}$. That is, if we order the edges of $G$ as $E = \{e_1, e_2, \dots, e_m\}$, then a cycle $C$ corresponds to a vector $x \in \mathbb F_2^m$ such that $$x_i = \begin{cases} 1 & e_i \in C, \\ 0 & e_i \notin C.\end{cases}$$ Then a collection of cycles $\mathcal C$ is redundant precisely when the corresponding vectors sum to $0$ (that is, the zero element of $\mathbb F_2^m$), and a redundant subset of $\mathcal D$ is a linear dependency.

(Over $\mathbb F_2$, a subset that sums to $0$ is the only kind of linear dependency you can have, since coefficients are always either $0$ or $1$.)

As a result, a collection of cycles $\mathcal D$ is independent, by this definition, precisely when it corresponds to a linearly independent collection of vectors in $\mathbb F_2^m$. It's easy to check that linearly independent sets over any vector space satisfy the properties of a matroid.

$\endgroup$
4
$\begingroup$

Suppose you want to count the cycles in a ladder graph.

enter image description here

Clearly it looks as though a ladder graph with $n$ rungs is made of $n-1$ cycles glued together. However, if you count all possible cycles, you find $\binom n2$ of them (choose any two rungs and take the rectangle between them). The notion of independent cycles formalizes the former intuition; all independent sets of cycles have $n-1$ elements.

$\endgroup$

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.