Bipartite matroid


In mathematics, a bipartite matroid is a matroid all of whose circuits have even size.

Example

A uniform matroid is bipartite if and only if is an odd number, because the circuits in such a matroid have size.

Relation to bipartite graphs

Eulerian matroids were defined by 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 is non-bipartite but its dual is Eulerian, as it can be partitioned into two 3-cycles. The self-dual uniform matroid 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.