Q&A

This is a page for your matroid-related queries that don’t belong with any particular article on the blog. Post your question in the comments, and hopefully someone will be able to help you!

8 thoughts on “Q&A

  1. Question from Luis Goddyn

    Question for y’all,
    Here is a partial list of complete matroid classes (closed under minors, duals, direct sums, principal extensions). Each class in the list is properly contained in its predecessors. (In fact, M(K_4) is a minimal excluded minor for each class.)
    1. M(K_4)-free
    2. Base orderable
    3. k-base orderable (k=2,3,…)
    4. Strongly base orderable
    5. Gammoids
    Now, every gammoid is orientable (indeed R-representable).
    Q1. Does another class in this list consist entirely of orientable (or R-representable) matroids?
    Q2. Is there a non-orientable matroid without M(K_4) minor?
    I have not found much helpful literature so far.

    • Hi Luis, interesting questions!

      I don’t know enough about orientable matroids to have proper intuition. I can give an answer to Q1 part (ii) (the answer is no) and for what it’s worth, I think the answer to Q2 will be yes.

      Take AG(2,3), the ternary affine plane. The appendix in Oxley’s book tells us that it has no M(K_4)-minor. It is not real-representable, so no class in your list contains only real-representable matroids.

      On the other hand, AG(2,3) is base-orderable, and therefore orientable. So I used Sage to construct ternary coextensions of AG(2,3) that do not have M(K_4), in the hope that some of them will be non-orientable. Here’s an example, represented over GF(3):

      [1 2 1 2 1 2 1 2 1 0]
      [0 0 1 1 2 2 1 1 0 0]
      [1 1 1 1 1 1 0 0 0 0]
      [0 0 1 1 0 1 2 0 2 1]

      But now I’m stuck, because I don’t know how to quickly test whether this is non-orientable.

      Cheers,

      Dillon

      EDIT: I got the order of subclass inclusion wrong, so of course AG(2,3)
      tells us nothing about any of the classes other than Class (1), the
      matroids with no M(K_4)-minor. This class certainly contains
      matroids that are not real-representable.

      I can now do better than that, and show that Class (1) contains
      non-orientable matroids. In their paper Orientability of
      Matroids
      , Bland and Las Vergnas call the following matroid the
      MacLane matroid, and refer to the paper Representation of
      matroids
      , by Ingleton. Ingleton in turn refers to the 1936 paper
      Some interpretations of abstract linear dependence in terms of
      projective geometry
      by Saunders MacLane, but MacLane credits the
      configuration to Friedrich Levi, in Geometrische
      Konfigurationen
      , of 1931!

      In any case, I entered the matroid into Sage with the following command:

      M=Matroid(groundset=[‘a’,’b’,’c’,’v’,’x1′,’x2′,’y’,’z’],
      circuit_closures=[(2,{‘a’,’b’,’c’}),(2,{‘a’,’v’,’x2′}),(2,{‘a’,’x1′,’y’}
      ),(2,{‘b’,’x1′,’x2′}),(2,{‘b’,’y’,’z’}),(2,{‘c’,’v’,’y’}),(2,{‘c’,’x2′,’
      z’}),(2,{‘v’,’x1′,’z’}),(3,{‘a’,’b’,’c’,’v’,’x1′,’x2′,’y’,’z’})])

      Bland and Las Vergnas state that M is an excluded minor for the class of
      orientable matroids (p. 114). On the other hand, if I ask Sage:

      M.has_minor(matroids.CompleteGraphic(4))

      it reports

      False.

      So M is an example of a M(K_4)-free matroid that is non-orientable.

      • UPDATE: Luis pointed out that the MacLane matroid is actually just $AG(3,2)\backslash e$. So this matroid is not orientable. On the other hand, Lemma (4.4) in Oxley’s paper “A characterisation of the ternary matroids with no $M(K_{4})$-minor” says that a ternary rank-$3$ matroid is strongly base-orderable if and only if it has no $M(K_{4})$-minor. Since this property holds for $AG(3,2)\backslash e$, it is strongly base-orderable, and not orientable. So the answer to Luis’s Q1 is no: every one of his classes, other than the class of gammoids, contains non-orientable matroids.

  2. Dear all,
    I am looking for a general context in Matroid theory in which any finite rank closed
    set cannot be written as a finite union of closed sets of of smaller rank.
    Thank you.

  3. Add to a matroid a point and a circuits containing it. Is it true that the freest matroid containing this point and the circuit has the rank not less than the rank of the initial matroid (thus, equals it)?

  4. Hi, this blog may be exactly what I’m looking for. I have a question about fundamental circuits in binary matroids.

    I understand that every basis in a binary matroid has a set of fundamental circuits and that a set of fundamental circuits for any given basis completely defines the binary matroid. Is there a result or algorithm for finding the basis of a matroid with the fewest odd fundamental circuits? That is, fundamental circuits with an odd number of elements. Assume that the elements of the matroid are unique.

    • I am reasonably confident that this problem has not been considered. At least, it doesn’t ring any bells for me. I don’t immediately see a solution, but I will think some more about it.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.