Binary matroid

From formulasearchengine
Jump to navigation Jump to search

In matroid theory, a binary matroid is a matroid that can be represented over the finite field GF(2).[1] That is, up to isomorphism, they are the matroids whose elements are the columns of a (0,1)-matrix and whose sets of elements are independent if and only if the corresponding columns are linearly independent in GF(2).

Alternative characterizations

A matroid is binary if and only if

Related matroids

Every regular matroid, and every graphic matroid, is binary.[5] A binary matroid is regular if and only if it does not contain the Fano plane (a seven-element non-regular binary matroid) or its dual as a minor.[9] A binary matroid is graphic if and only if its minors do not include the dual of the graphic matroid of nor of .[10] If every circuit of a binary matroid has odd cardinality, then its circuits must all be disjoint from each other; in this case, it may be represented as the graphic matroid of a cactus graph.[5]

Additional properties

If is a binary matroid, then so is its dual, and so is every minor of .[5] Additionally, the direct sum of binary matroids is binary.

Template:Harvtxt define a bipartite matroid to be a matroid in which every circuit has even cardinality, and an Eulerian matroid to be a matroid in which the elements can be partitioned into disjoint circuits. Within the class of graphic matroids, these two properties describe the matroids of bipartite graphs and Eulerian graphs (not-necessarily-connected graphs in which all vertices have even degree), respectively. For planar graphs (and therefore also for the graphic matroids of planar graphs) these two properties are dual: a planar graph or its matroid is bipartite if and only if its dual is Eulerian. The same is true for binary matroids. However, there exist non-binary matroids for which this duality breaks down.[5][11]

Any algorithm that tests whether a given matroid is binary, given access to the matroid via an independence oracle, must perform an exponential number of oracle queries, and therefore cannot take polynomial time.[12]

References

  1. {{#invoke:citation/CS1|citation |CitationClass=citation }}.
  2. {{#invoke:citation/CS1|citation |CitationClass=citation }}.
  3. {{#invoke:citation/CS1|citation |CitationClass=citation }}. Reprinted in Template:Harvtxt, pp. 55–79.
  4. 4.0 4.1 4.2 4.3 Template:Harvtxt, Theorem 10.1.3, p. 162.
  5. 5.0 5.1 5.2 5.3 5.4 5.5 {{#invoke:citation/CS1|citation |CitationClass=citation }}.
  6. {{#invoke:citation/CS1|citation |CitationClass=citation }}.
  7. {{#invoke:citation/CS1|citation |CitationClass=citation }}.
  8. 8.0 8.1 Template:Harvtxt, Section 10.2, "An excluded minor criterion for a matroid to be binary", pp. 167–169.
  9. Template:Harvtxt, Theorem 10.4.1, p. 175.
  10. Template:Harvtxt, Theorem 10.5.1, p. 176.
  11. {{#invoke:citation/CS1|citation |CitationClass=citation }}/
  12. {{#invoke:citation/CS1|citation |CitationClass=citation }}.