Bipartite matroid

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$.

Bipartite matroids were defined by {{harvtxt|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.{{citation

| last = Welsh | first = D. J. A. | authorlink = Dominic Welsh

| journal = Journal of Combinatorial Theory

| mr = 0237368

| pages = 375–377

| title = Euler and bipartite matroids

| volume = 6

| year = 1969

| issue = 4 | doi=10.1016/s0021-9800(69)80033-5| doi-access = free

}}.

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.

It is possible to test in polynomial time whether a given binary matroid is bipartite.{{citation

| last1 = Lovász | first1 = László | author1-link = László Lovász

| last2 = Seress | first2 = Ákos

| doi = 10.1006/eujc.1993.1027

| issue = 3

| journal = European Journal of Combinatorics

| mr = 1215334

| pages = 241–250

| title = The cocycle lattice of binary matroids

| volume = 14

| year = 1993| doi-access = free

}}. 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.{{citation

| last1 = Jensen | first1 = Per M.

| last2 = Korte | first2 = Bernhard

| doi = 10.1137/0211014

| issue = 1

| journal = SIAM Journal on Computing

| mr = 646772

| pages = 184–190

| title = Complexity of matroid property algorithms

| volume = 11

| year = 1982}}.

{{reflist}}

Category:Matroid theory