Skip to main content
add combinatorics tag, fix typos
Source Link
j.c.
  • 13.6k
  • 3
  • 52
  • 90

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$$G_1$ is bipartite and equals $V_1$ if $G_1$ has an odd cycle.

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

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$ is bipartite and equals $V_1$ if $G_1$ has an odd cycle.

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

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.

Source Link
Fedor Petrov
  • 108.8k
  • 9
  • 264
  • 459

Matroids similar to the cycle matroid

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$ is bipartite and equals $V_1$ if $G_1$ has an odd cycle.

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