Английская Википедия:Binary matroid
Шаблон:Short description 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 <math>M</math> is binary if and only if
- It is the matroid defined from a symmetric (0,1)-matrix.[2]
- 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.[3][4]
- For every pair of circuits of the matroid, their symmetric difference contains another circuit.[4]
- 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.[4][5]
- 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>.[4][5]
- No matroid minor of <math>M</math> is the uniform matroid <math>U{}^2_4</math>, 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 <math>K_5</math> nor of <math>K_{3,3}</math>.[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 <math>M</math> is a binary matroid, then so is its dual, and so is every minor of <math>M</math>.[5] Additionally, the direct sum of binary matroids is binary.
Шаблон:Harvtxt 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
- ↑ Шаблон:Citation.
- ↑ Шаблон:Citation.
- ↑ Шаблон:Citation.
- ↑ 4,0 4,1 4,2 4,3 Шаблон:Harvtxt, Theorem 10.1.3, p. 162.
- ↑ 5,0 5,1 5,2 5,3 5,4 5,5 Шаблон:Citation.
- ↑ Шаблон:Citation.
- ↑ Шаблон:Citation.
- ↑ 8,0 8,1 Шаблон:Harvtxt, Section 10.2, "An excluded minor criterion for a matroid to be binary", pp. 167–169.
- ↑ Шаблон:Harvtxt, Theorem 10.4.1, p. 175.
- ↑ Шаблон:Harvtxt, Theorem 10.5.1, p. 176.
- ↑ Шаблон:Citation/
- ↑ Шаблон:Citation.
