Binary matroid

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 ${\displaystyle M}$ is binary if and only if

• It is the matroid defined from a symmetric (0,1)-matrix. ^[2]
• For every set ${\displaystyle {\mathcal {S}}}$ of circuits of the matroid, the symmetric difference of the circuits in ${\displaystyle {\mathcal {S}}}$ can be represented as a disjoint union of circuits. ^{[3] [4]}
• For every pair of circuits of the matroid, their symmetric difference contains another circuit. ^[4]
• For every pair ${\displaystyle C,D}$ where ${\displaystyle C}$ is a circuit of ${\displaystyle M}$ and ${\displaystyle D}$ is a circuit of the dual matroid of ${\displaystyle M}$, ${\displaystyle |C\cap D|}$ is an even number. ^{[4] [5]}
• For every pair ${\displaystyle B,C}$ where ${\displaystyle B}$ is a basis of ${\displaystyle M}$ and ${\displaystyle C}$ is a circuit of ${\displaystyle M}$, ${\displaystyle C}$ is the symmetric difference of the fundamental circuits induced in ${\displaystyle B}$ by the elements of ${\displaystyle C\setminus B}$. ^{[4] [5]}
• No matroid minor of ${\displaystyle M}$ is the uniform matroid ${\displaystyle U{}_{4}^{2}}$, the four-point line. ^{[6] [7] [8]}
• In the geometric lattice associated to the matroid, every interval of height two has at most five elements. ^[8]

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 ${\displaystyle K_{5}}$ nor of ${\displaystyle K_{3,3}}$. ^[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 ${\displaystyle M}$ is a binary matroid, then so is its dual, and so is every minor of ${\displaystyle M}$. ^[5] Additionally, the direct sum of binary matroids is binary.

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. ^{[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. Welsh, D. J. A. (2010) [1976], "10. Binary Matroids", Matroid Theory, Courier Dover Publications, pp. 161–182, ISBN   9780486474397 .
2. Jaeger, F. (1983), "Symmetric representations of binary matroids", Combinatorial mathematics (Marseille-Luminy, 1981), North-Holland Math. Stud., vol. 75, Amsterdam: North-Holland, pp. 371–376, MR   0841317 .
3. Whitney, Hassler (1935), "On the abstract properties of linear dependence", American Journal of Mathematics, The Johns Hopkins University Press, 57 (3): 509–533, doi:10.2307/2371182, hdl: 10338.dmlcz/100694 , JSTOR   2371182, MR   1507091 .
4. Welsh (2010), Theorem 10.1.3, p. 162.
5. Harary, Frank; Welsh, Dominic (1969), "Matroids versus graphs", The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968), Lecture Notes in Mathematics, vol. 110, Berlin: Springer, pp. 155–170, doi:10.1007/BFb0060114, MR   0263666 .
6. Tutte, W. T. (1958), "A homotopy theorem for matroids. I, II", Transactions of the American Mathematical Society , 88 (1): 144–174, doi:10.2307/1993244, JSTOR   1993244, MR   0101526 .
7. Tutte, W. T. (1965), "Lectures on matroids", Journal of Research of the National Bureau of Standards, 69B: 1–47, doi: 10.6028/jres.069b.001 , MR   0179781 .
8. Welsh (2010), Section 10.2, "An excluded minor criterion for a matroid to be binary", pp. 167–169.
9. Welsh (2010), Theorem 10.4.1, p. 175.
10. Welsh (2010), Theorem 10.5.1, p. 176.
11. Welsh, D. J. A. (1969), "Euler and bipartite matroids", Journal of Combinatorial Theory , 6 (4): 375–377, doi: 10.1016/s0021-9800(69)80033-5 , MR   0237368 /
12. Seymour, P. D. (1981), "Recognizing graphic matroids", Combinatorica , 1 (1): 75–78, doi:10.1007/BF02579179, MR   0602418, S2CID   35579707 .