Binary matroid: Difference between revisions

Content deleted Content added

Inline

Latest revision as of 00:12, 9 November 2024

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., 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, hdl:10338.dmlcz/100694, JSTOR 2371182, MR 1507091.
^ ^a ^b ^c ^d Welsh (2010), Theorem 10.1.3, p. 162.
^ ^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, ISBN 978-3-540-04629-5, MR 0263666.
^ 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.
^ 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.
^ ^a ^b 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 (4): 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 0602418, S2CID 35579707.

[w76-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, 57 (3), The Johns Hopkins University Press: 509–533, doi:10.2307/2371182, hdl:10338.dmlcz/100694, JSTOR 2371182, MR 1507091.

[w-thm3-4] Welsh (2010), Theorem 10.1.3, p. 162.

[vs-5] ^ ^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, ISBN 978-3-540-04629-5, 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.

[tutte-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.

[w-10-2-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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

@@ Line 1: / Line 1: @@
+{{Short description|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)]]. That is, up to isomorphism, they are the matroids whose elements are the columns of a [[Logical matrix|(0,1)-matrix]] and whose sets of elements are independent if and only if the submatrix that they form has an odd [[determinant]].
+In [[Matroid|matroid theory]], a '''binary matroid''' is a matroid that can be [[Matroid representation|represented]] over the [[finite field]] [[GF(2)]].<ref name="w76">{{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}}.</ref> That is, up to isomorphism, they are the matroids whose elements are the columns of a [[Logical matrix|(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==
@@ Line 14: / Line 22: @@
  | volume = 75
  | year = 1983}}.</ref>
-*For every set <math>\mathcal{S}</math> of circuits of the matroid, the [[symmetric difference]] of the circuits in <math>\mathcal{S}</math> can be represented as a [[disjoint union]] of circuits.<ref>{{citation|last=Whitney|first=Hassler|authorlink=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}}. Reprinted in {{harvtxt|Kung|1986}}, pp.&nbsp;55–79.</ref>
+*For every set <math>\mathcal{S}</math> of circuits of the matroid, the [[symmetric difference]] of the circuits in <math>\mathcal{S}</math> can be represented as a [[disjoint union]] of circuits.<ref>{{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}}.</ref><ref name="w-thm3">{{harvtxt|Welsh|2010}}, Theorem 10.1.3, p. 162.</ref>
-*For every pair <math>C,D</math> where <math>C</math> is a circuit of <math>M</math> and <math>D</math> is a circuit of the dual matroid of <math>M</math>, <math>|C\cap D|</math> is an even number.<ref name="vs">{{citation
+*For every pair of circuits of the matroid, their symmetric difference contains another circuit.<ref name="w-thm3"/>
+*For every pair <math>C,D</math> where <math>C</math> is a circuit of <math>M</math> and <math>D</math> is a circuit of the [[dual matroid]] of <math>M</math>, <math>|C\cap D|</math> is an even number.<ref name="w-thm3"/><ref name="vs">{{citation
  | last1 = Harary | first1 = Frank | author1-link = Frank Harary
  | last2 = Welsh | first2 = Dominic | author2-link = Dominic Welsh
@@ Line 27: / Line 36: @@
  | title = The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968)
  | volume = 110
- | year = 1969}}.</ref>
+ | isbn = 978-3-540-04629-5 | year = 1969}}.</ref>
-*For every pair <math>B,C</math> where <math>B</math> is a basis of <math>M</math> and <math>C</math> is a circuit of <math>M</math>, <math>C</math> is the symmetric difference of the fundamental circuits induced in <math>B</math> by the elements of <math>C\setminus B</math>.<ref name="vs"/>
+*For every pair <math>B,C</math> where <math>B</math> is a basis of <math>M</math> and <math>C</math> is a circuit of <math>M</math>, <math>C</math> is the symmetric difference of the fundamental circuits induced in <math>B</math> by the elements of <math>C\setminus B</math>.<ref name="w-thm3"/><ref name="vs"/>
 *No [[matroid minor]] of <math>M</math> is the [[uniform matroid]] <math>U{}^2_4</math>, the four-point line.<ref>{{citation
- | last = Tutte | first = W. T. | authorlink = W. T. Tutte
+ | last = Tutte | first = W. T. | author-link = W. T. Tutte
  | journal = [[Transactions of the American Mathematical Society]]
  | mr = 0101526
@@ Line 36: / Line 45: @@
  | title = A homotopy theorem for matroids. I, II
  | volume = 88
- | year = 1958}}.</ref><ref name="tutte">{{citation
+ | year = 1958
+ | issue = 1 | doi=10.2307/1993244| jstor = 1993244 }}.</ref><ref name="tutte">{{citation
  | last = Tutte | first = W. T.
  | journal = Journal of Research of the National Bureau of Standards
@@ Line 44: / Line 54: @@
  | url = http://cdm16009.contentdm.oclc.org/cdm/ref/collection/p13011coll6/id/66650
  | volume = 69B
- | year = 1965}}.</ref>
+ | year = 1965
+ | doi=10.6028/jres.069b.001| doi-access = free
+ }}.</ref><ref name="w-10-2">{{harvtxt|Welsh|2010}}, Section 10.2, "An excluded minor criterion for a matroid to be binary", pp. 167–169.</ref>
+*In the [[geometric lattice]] associated to the matroid, every interval of height two has at most five elements.<ref name="w-10-2"/>
 ==Related matroids==
-Every [[regular matroid]], and every [[graphic matroid]], is binary.<ref name="vs"/> 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]].<ref name="vs"/>
+Every [[regular matroid]], and every [[graphic matroid]], is binary.<ref name="vs"/> 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 [[matroid minor|minor]].<ref>{{harvtxt|Welsh|2010}}, Theorem 10.4.1, p. 175.</ref> A binary matroid is graphic if and only if its minors do not include the dual of the graphic matroid of <math>K_5</math> nor of <math>K_{3,3}</math>.<ref>{{harvtxt|Welsh|2010}}, Theorem 10.5.1, p. 176.</ref> 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]].<ref name="vs"/>
 ==Additional properties==
@@ Line 53: / Line 66: @@
 {{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
+ | last = Welsh | first = D. J. A. | author-link = Dominic Welsh
  | journal = [[Journal of Combinatorial Theory]]
  | mr = 0237368
@@ Line 59: / Line 72: @@
  | title = Euler and bipartite matroids
  | volume = 6
- | year = 1969}}
+ | year = 1969
+ | issue = 4 | doi=10.1016/s0021-9800(69)80033-5| doi-access = free
+ }}/</ref>
+Any algorithm that tests whether a given matroid is binary, given access to the matroid via an [[matroid oracle|independence oracle]], must perform an exponential number of oracle queries, and therefore cannot take polynomial time.<ref>{{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 }}.</ref>
 ==References==
-{{reflist}}
+{{reflist|colwidth=30em}}
 [[Category:Matroid theory]]