Trisha Shetty (Editor)

Binary matroid

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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 corresponding columns are linearly independent in GF(2).

Contents

Alternative characterizations

A matroid M is binary if and only if

  • It is the matroid defined from a symmetric (0,1)-matrix.
  • For every set S of circuits of the matroid, the symmetric difference of the circuits in S can be represented as a disjoint union of circuits.
  • For every pair of circuits of the matroid, their symmetric difference contains another circuit.
  • For every pair C , D where C is a circuit of M and D is a circuit of the dual matroid of M , | C ∩ D | is an even number.
  • 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 ∖ B .
  • No matroid minor of M is the uniform matroid U 4 2 , the four-point line.
  • In the geometric lattice associated to the matroid, every interval of height two has at most five elements.

    • Every regular matroid, and every graphic matroid, is binary. 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. 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 . 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.

    Additional properties

    If M is a binary matroid, then so is its dual, and so is every minor of M . 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.

    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.

    References

    Binary matroid Wikipedia
    (Text) CC BY-SA