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!
The Matroid Union
A blog for and by the matroid community
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!
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.
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.
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)?
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.
I suspect that the answer is no because determining the frustration index of a signed graph is NP-hard (https://en.wikipedia.org/wiki/Signed_graph#Frustration_index). I’m pretty sure that the frustration index of a connected signed graph is equal to the minimum, over all spanning trees, of the number of odd fundamental circuits. Then take the frame matroid of the signed graph…