binary matroid

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 $\backslash mathcal\{S\}$ of circuits of the matroid, the symmetric difference of the circuits in $\backslash mathcal\{S\}$ can be represented as a disjoint union of circuits.{{citation|last=Whitney|first=Hassler|author-link=Hassler Whitney|year=1935|title=On the abstract properties of linear dependence|journal=American Journal of Mathematics|volume=57|pages=509–533|doi=10.2307/2371182|issue=3|publisher=The Johns Hopkins University Press|mr=1507091|jstor=2371182|hdl=10338.dmlcz/100694|hdl-access=free}}.{{harvtxt|Welsh|2010}}, Theorem 10.1.3, p. 162.
• 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\backslash 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\backslash 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

}}.{{harvtxt|Welsh|2010}}, Section 10.2, "An excluded minor criterion for a matroid to be binary", pp. 167–169.

• In the geometric lattice associated to the matroid, every interval of height two has at most five elements.

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.{{harvtxt|Welsh|2010}}, Theorem 10.4.1, p. 175. 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\}$.{{harvtxt|Welsh|2010}}, Theorem 10.5.1, p. 176. 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.

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.

{{harvtxt|Harary|Welsh|1969}} 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 }}.

{{reflist|colwidth=30em}}

Category:Matroid theory