Bipartite matroid
In mathematics, a bipartite matroid is a matroid all of whose circuits have even size.
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In mathematics, a bipartite matroid is a matroid all of whose circuits have even size.
Example
A uniform matroid U{}^r_n is bipartite if and only if r is an odd number, because the circuits in such a matroid have size r+1 .
Relation to bipartite graphs
Bipartite 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 U{}^4_6 is non-bipartite but its dual U{}^2_6 is Eulerian, as it can be partitioned into two 3-cycles. The self-dual uniform matroid U{}^3_6 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.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1136196454 under CC BY-SA 4.0; modifications have been made.