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.