Bipartite matroid

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

Uses your system voice; voice and rate in settings.

Snapshot

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

Provenance

snapshot enwiki-001136196454 · captured 2023-01-29 · not yet sealed in the ledger · verify the chain · version history

Cite this page as: encyclopegia.org, “Bipartite matroid”, snapshot enwiki-001136196454. https://encyclopegia.org/a/bipartite-matroid

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.