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!

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 GoddynQuestion 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, Bland and Las Vergnas call the following matroid theMatroids

MacLane matroid, and refer to the paperRepresentation of, by Ingleton. Ingleton in turn refers to the 1936 papermatroids

Some interpretations of abstract linear dependence in terms ofby Saunders MacLane, but MacLane credits theprojective geometry

configuration to Friedrich Levi, in

Geometrische, of 1931!Konfigurationen

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…