Binary matroid

Quality 0.50 · 3 views · Updated 2 months ago

Abstraction of mod-2 vector independence

title: "Binary matroid" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["matroid-theory"] description: "Abstraction of mod-2 vector independence" topic_path: "general/matroid-theory" source: "https://en.wikipedia.org/wiki/Binary_matroid" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Abstraction of mod-2 vector independence ::

In matroid theory, a binary matroid is a matroid that can be represented over the finite field GF(2).{{citation | last = Welsh | first = D. J. A. | author-link = Dominic Welsh | contribution = 10. Binary Matroids | isbn = 9780486474397 | pages = 161–182 | publisher = Courier Dover Publications | title = Matroid Theory | year = 2010 | orig-year=1976}}. 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 M is binary if and only if

  • It is the matroid defined from a symmetric (0,1)-matrix.{{citation | last = Jaeger | first = F. | contribution = Symmetric representations of binary matroids | location = Amsterdam | mr = 841317 | pages = 371–376 | publisher = North-Holland | series = North-Holland Math. Stud. | title = Combinatorial mathematics (Marseille-Luminy, 1981) | volume = 75 | year = 1983}}.
  • For every set \mathcal{S} of circuits of the matroid, the symmetric difference of the circuits in \mathcal{S} can be represented as a disjoint union of circuits.
  • For every pair of circuits of the matroid, their symmetric difference contains another circuit.
  • For every pair C,D where C is a circuit of M and D is a circuit of the dual matroid of M, |C\cap D| is an even number.{{citation | last1 = Harary | first1 = Frank | author1-link = Frank Harary | last2 = Welsh | first2 = Dominic | author2-link = Dominic Welsh | contribution = Matroids versus graphs | doi = 10.1007/BFb0060114 | location = Berlin | mr = 0263666 | pages = 155–170 | publisher = Springer | series = Lecture Notes in Mathematics | title = The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968) | volume = 110 | isbn = 978-3-540-04629-5 | year = 1969}}.
  • For every pair B,C where B is a basis of M and C is a circuit of M, C is the symmetric difference of the fundamental circuits induced in B by the elements of C\setminus B.
  • No matroid minor of M is the uniform matroid U{}^2_4, the four-point line.{{citation | last = Tutte | first = W. T. | author-link = W. T. Tutte | journal = Transactions of the American Mathematical Society | mr = 0101526 | pages = 144–174 | title = A homotopy theorem for matroids. I, II | volume = 88 | year = 1958 | issue = 1 | doi=10.2307/1993244| jstor = 1993244 }}.{{citation | last = Tutte | first = W. T. | journal = Journal of Research of the National Bureau of Standards | mr = 0179781 | pages = 1–47 | title = Lectures on matroids | url = http://cdm16009.contentdm.oclc.org/cdm/ref/collection/p13011coll6/id/66650 | volume = 69B | year = 1965 | doi=10.6028/jres.069b.001| doi-access = free
  • In the geometric lattice associated to the matroid, every interval of height two has at most five elements.

Related matroids

Every regular matroid, and every graphic matroid, is binary. 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. A binary matroid is graphic if and only if its minors do not include the dual of the graphic matroid of K_5 nor of K_{3,3}. 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.

Additional properties

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

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.{{citation | last = Welsh | first = D. J. A. | author-link = 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

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.{{citation | last = Seymour | first = P. D. | author-link = Paul Seymour (mathematician) | doi = 10.1007/BF02579179 | issue = 1 | journal = Combinatorica | mr = 602418 | pages = 75–78 | title = Recognizing graphic matroids | volume = 1 | year = 1981| s2cid = 35579707 }}.

References

References

  1. Whitney, Hassler. (1935). "On the abstract properties of linear dependence". The Johns Hopkins University Press.
  2. {{harvtxt. Welsh. 2010, Theorem 10.1.3, p. 162.
  3. {{harvtxt. Welsh. 2010, Section 10.2, "An excluded minor criterion for a matroid to be binary", pp. 167–169.
  4. {{harvtxt. Welsh. 2010, Theorem 10.4.1, p. 175.
  5. {{harvtxt. Welsh. 2010, Theorem 10.5.1, p. 176.

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::

matroid-theory