Bipartite matroid
In mathematics, a bipartite matroid is a matroid all of whose circuits have even size.
Example
A uniform matroid [math]\displaystyle{ U{}^r_n }[/math] is bipartite if and only if [math]\displaystyle{ r }[/math] is an odd number, because the circuits in such a matroid have size [math]\displaystyle{ r+1 }[/math].
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.[1]
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 [math]\displaystyle{ U{}^4_6 }[/math] is non-bipartite but its dual [math]\displaystyle{ U{}^2_6 }[/math] is Eulerian, as it can be partitioned into two 3-cycles. The self-dual uniform matroid [math]\displaystyle{ U{}^3_6 }[/math] is bipartite but not Eulerian.
Computational complexity
It is possible to test in polynomial time whether a given binary matroid is bipartite.[2] 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.[3]
References
- ↑ "Euler and bipartite matroids", Journal of Combinatorial Theory 6 (4): 375–377, 1969, doi:10.1016/s0021-9800(69)80033-5.
- ↑ "The cocycle lattice of binary matroids", European Journal of Combinatorics 14 (3): 241–250, 1993, doi:10.1006/eujc.1993.1027.
- ↑ Jensen, Per M.; Korte, Bernhard (1982), "Complexity of matroid property algorithms", SIAM Journal on Computing 11 (1): 184–190, doi:10.1137/0211014.
 |  |
