10
$\begingroup$

Let $G=(V,E)$ be a graph (loops and multiple edges are permitted). Three following systems of dependent sets in $E$ define matroids:

1) Set $A\subset E$ is dependent if $A$ contains cycle. This is a cycle matroid, maybe the most popular matroid.

2) Set $A\subset E$ is dependent if $A$ contains two different cycles in the same connected component. In other words, independent set is characterized by the property that number of edges in any connected component does not exceed number of vertices.

3) Set $A\subset E$ is dependent if $A$ contains either even cycle or two odd cycles in the same connected component. In other words, rank of a connected subgraph $G_1=(V_1,E_1)$ equals $|V_1|-1$ if $G_1$ is bipartite and equals $V_1$ if $G_1$ has an odd cycle.

My question is whether these examples may be included in a more large picture, and may I read about those matroids.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
6
$\begingroup$

The first two examples fall neatly into the class of $(k,l)$-sparsity matroids (see the references in this Wikipedia article and references contained within). The cycle matroid (1) is the (1,1)-sparsity matroid on $G$ and the second matroid you describe is the (1,0)-sparsity matroid.

The third example is an example of a frame matroid and has been called the "even-circle matroid". It appears in a paper of Doob on the eigenspace of -2 of the adjacency matrix of a graph, and in Zaslavsky's paper "Biased Graphs I" (the first in the series linked by Gordon Royle) it appears as example 6.3. (Note that what Zaslavsky calls bias matroids are now called frame matroids).

There are some common generalizations of sparsity matroids and frame matroids, see e.g. these papers by Tanigawa.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Just to add, if $(k,l)$-sparsity matroids are the generalisation you are interested in, then the natural way to start is with Nash-Williams result: the $(k,k)$-tight count is equivalent to $k$ edge-disjoint spanning trees. So the $(k,k)$-sparse matroid is the union of $k$ cycle matroids. Then, for example, the $(2,3)$-sparse matroid is formed from the $(2,2)$-sparse matroid by a Dilworth truncation. $\endgroup$
    – user62562
    Commented Aug 5, 2015 at 12:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .