Binary matroid: Difference between revisions
→Additional properties: cite the paper of Welsh that this result originally was published in |
|||
| Line 52: | Line 52: | ||
If <math>M</math> is a binary matroid, then so is its dual, and so is every [[matroid minor|minor]] of <math>M</math>.<ref name="vs"/> Additionally, the direct sum of binary matroids is binary. |
If <math>M</math> is a binary matroid, then so is its dual, and so is every [[matroid minor|minor]] of <math>M</math>.<ref name="vs"/> 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 graph]]s and [[Eulerian graph]]s (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.<ref name="vs"/> |
{{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 graph]]s and [[Eulerian graph]]s (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.<ref name="vs"/><ref>{{citation |
||
| last = Welsh | first = D. J. A. | authorlink = Dominic Welsh |
|||
| journal = [[Journal of Combinatorial Theory]] |
|||
| mr = 0237368 |
|||
| pages = 375–377 |
|||
| title = Euler and bipartite matroids |
|||
| volume = 6 |
|||
| year = 1969}} |
|||
==References== |
==References== |
||
Revision as of 18:59, 28 August 2012
In matroid theory, a binary matroid is a matroid that can be represented over the finite field GF(2). 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 submatrix that they form has an odd determinant.
Alternative characterizations
A matroid is binary if and only if
- It is the matroid defined from a symmetric (0,1)-matrix.[1]
- For every set of circuits of the matroid, the symmetric difference of the circuits in can be represented as a disjoint union of circuits.[2]
- For every pair where is a circuit of and is a circuit of the dual matroid of , is an even number.[3]
- For every pair where is a basis of and is a circuit of , is the symmetric difference of the fundamental circuits induced in by the elements of .[3]
- No matroid minor of is the uniform matroid , the four-point line.[4][5]
Related matroids
Every regular matroid, and every graphic matroid, is binary.[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.[3]
Additional properties
If is a binary matroid, then so is its dual, and so is every minor of .[3] 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.[3]<ref>Welsh, D. J. A. (1969), "Euler and bipartite matroids", Journal of Combinatorial Theory, 6: 375–377, MR 0237368
References
- ^ 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.
- ^ Whitney, Hassler (1935), "On the abstract properties of linear dependence", American Journal of Mathematics, 57 (3), The Johns Hopkins University Press: 509–533, doi:10.2307/2371182, JSTOR 2371182, MR 1507091. Reprinted in Kung (1986), pp. 55–79.
- ^ a b c d e f 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.
- ^ Tutte, W. T. (1958), "A homotopy theorem for matroids. I, II", Transactions of the American Mathematical Society, 88: 144–174, MR 0101526.
- ^ Tutte, W. T. (1965), "Lectures on matroids", Journal of Research of the National Bureau of Standards, 69B: 1–47, MR 0179781.