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 $M$ is binary if and only if

It is the matroid defined from a symmetric (0,1)-matrix.^[2]
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.^[3]^[4]
For every pair of circuits of the matroid, their symmetric difference contains another circuit.^[4]
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.^[4]^[5]
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$ .^[4]^[5]
No matroid minor of $M$ is the uniform matroid $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 $K_{5}$ nor of $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 $M$ is a binary matroid, then so is its dual, and so is every minor of $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

↑ Welsh, D. J. A. (2010) [1976], "10. Binary Matroids", Matroid Theory, Courier Dover Publications, pp. 161–182, ISBN 9780486474397 .
↑ Jaeger, F. (1983), "Symmetric representations of binary matroids", Combinatorial mathematics (Marseille-Luminy, 1981), North-Holland Math. Stud., 75, Amsterdam: North-Holland, pp. 371–376, MR 841317 .
↑ 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, JSTOR 2371182, MR 1507091 . Reprinted in Kung (1986), pp. 55–79.
1 2 3 4 Welsh (2010), Theorem 10.1.3, p. 162.
1 2 3 4 5 6 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, 110, Berlin: Springer, pp. 155–170, doi:10.1007/BFb0060114, MR 0263666 .
↑ Tutte, W. T. (1958), "A homotopy theorem for matroids. I, II", Transactions of the American Mathematical Society, 88: 144–174, doi:10.2307/1993244, MR 0101526 .
↑ 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 .
1 2 Welsh (2010), Section 10.2, "An excluded minor criterion for a matroid to be binary", pp. 167–169.
↑ Welsh (2010), Theorem 10.4.1, p. 175.
↑ Welsh (2010), Theorem 10.5.1, p. 176.
↑ Welsh, D. J. A. (1969), "Euler and bipartite matroids", Journal of Combinatorial Theory, 6: 375–377, doi:10.1016/s0021-9800(69)80033-5, MR 0237368 /
↑ Seymour, P. D. (1981), "Recognizing graphic matroids", Combinatorica, 1 (1): 75–78, doi:10.1007/BF02579179, MR 602418 .

This article is issued from Wikipedia - version of the 6/8/2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.