- Source: Bipartite matroid
In mathematics, a bipartite matroid is a matroid all of whose circuits have even size.
Example
A uniform matroid
U
n
r
{\displaystyle U{}_{n}^{r}}
is bipartite if and only if
r
{\displaystyle r}
is an odd number, because the circuits in such a matroid have size
r
+
1
{\displaystyle r+1}
.
Relation to bipartite graphs
Bipartite matroids were defined by Welsh (1969) as a generalization of the bipartite graphs, graphs in which every cycle has even size. A graphic matroid is bipartite if and only if it comes from a bipartite graph.
Duality with Eulerian matroids
An Eulerian graph is one in which all vertices have even degree; Eulerian graphs may be disconnected. For planar graphs, the properties of being bipartite and Eulerian are dual: a planar graph is bipartite if and only if its dual graph is Eulerian. As Welsh showed, this duality extends to binary matroids: a binary matroid is bipartite if and only if its dual matroid is an Eulerian matroid, a matroid that can be partitioned into disjoint circuits.
For matroids that are not binary, the duality between Eulerian and bipartite matroids may break down. For instance, the uniform matroid
U
6
4
{\displaystyle U{}_{6}^{4}}
is non-bipartite but its dual
U
6
2
{\displaystyle U{}_{6}^{2}}
is Eulerian, as it can be partitioned into two 3-cycles. The self-dual uniform matroid
U
6
3
{\displaystyle U{}_{6}^{3}}
is bipartite but not Eulerian.
Computational complexity
It is possible to test in polynomial time whether a given binary matroid is bipartite. However, any algorithm that tests whether a given matroid is Eulerian, given access to the matroid via an independence oracle, must perform an exponential number of oracle queries, and therefore cannot take polynomial time.
References
Kata Kunci Pencarian:
- Bipartite matroid
- Graphic matroid
- Bipartite graph
- Matroid
- Eulerian matroid
- Delta-matroid
- Matroid intersection
- Binary matroid
- Dual matroid
- Matroid girth
