Matroids relaxations of a given matroid

Question

Let $\mathcal{M}$ be a rank-$d$ matroid on $[n]$. Say a matroid $\mathcal{N}$ is a relaxation of $\mathcal{M}$ if $\mathrm{rank}(\mathcal{N})=d$, $\mathrm{groundset}(\mathcal{N})=[n]$, and every independent set of $\mathcal{M}$ is an independent set of $\mathcal{N}$ (observe that this notion of relaxation is in the labeled sense).

Has anyone seen the set of all relaxations of $\mathcal{M}$ naturally show up in some context?

I'm particularly interested in the algorithmic task of listing all relaxations of a given matroid $\mathcal{M}$, and in any heuristic to make an implementation more efficient than performing the enumeration by brute force; it would be even better if such an implementation already exists.

Actually, I only care about those relaxations of $\mathcal{M}$ that are realizable over a fixed field, say $\mathbb{C}$, which brings me to the next question:

Does anyone know of an implementation of a (finite) algorithm that decides whether a matroid is representable and provides a representation in case it is? (that such a finite algorithm exists can be proved using Groebner bases)

Here I'm explicitly disregarding any complexity issues; I just want to be able to do compute a realization for some small matroids.

Note: the first question is different from the "opposite" one of listing all matroids that specialize a fixed matroid, which has been asked here. I wonder how different the task of listing all relaxations is.

---

Update: I implemented the following brute-force algorithm in sage to enumerate the relaxations of a rank-$d$ matroid on $[n]$:

For every subset $\mathcal{F}$ of the nonbases of $\mathcal{M}$, check whether $bases(\mathcal{M})\cup \mathcal{F}$is the collection of bases of a matroid.

According to sage's method .is_valid() for matroids, the outcome for all the matroids I tested was that all $2^{\#\{nonbases(\mathcal{M})\}}$ subsets of $\binom{[n]}{d}$ obtained form the bases of a matroid, which wasn't what I expected.

Can it be that there's a bug in sage's .is_valid() method, or is it actually to be expected that most naive relaxations of a matroid (as enumerated above) are actually matroids?

(the reward is independent from the update in the question)

Answer 1

You are describing what are usually called "weak maps" between matroids.

So a bijection $\varphi: E(\mathcal{N}) \to E(\mathcal{M})$ is called a weak map if for every independent set $I$ of $\mathcal{M}$ the inverse image $\varphi^{-1}(I)$ is independent in $\mathcal{N}$. In your case, you are asking when the identity function is a weak map, which just requires every independent set of $\mathcal{M}$ to be independent in $\mathcal{N}$.

There is lots of stuff known about weak maps (and strong maps) and other things. Given a bunch of matroids on the same ground set, the weak-map relation is a partial order. The best place to start is around page 280 of the second edition of Oxley's book Matroid Theory, which refers to the original papers.

The "minimal" relaxation that can be done is to take a single non-basis $N$ of $\mathcal{M}$ and form a matroid whose bases are ${\mathrm{bases}} (\mathcal{M}) \cup \{N\}$. This will work if (and, I think, only if) $N$ is a circuit-hyperplane of $\mathcal{M}$.

So you certainly do not expect all of your relaxations to pass Sage's is_valid routine.

In fact, I wanted to do a test to convince myself that it was working ok, so I ran the following code, just testing all the relaxations of a single randomly chosen matroid (in this case the matroid called J). All this does is create an array of matroids, each of which are specified by their bases, for which I am using the bases of J together with one of the non-bases. Then I ask is_valid() which of those matroids are valid.

m = matroids.named_matroids.J()
bases = [x for x in m.bases()]
nonbases = [x for x in m.nonbases()]
circuithyps = [x for x in m.circuits() if x in m.hyperplanes()]
tstsets = [bases + [nonbases[i]] for i in [0..len(nonbases)-1]]
tstmats = [Matroid(x) for x in tstsets]
tstcheck = [m.is_valid() for m in tstmats]
tstcheck

and I obtained the following result:

[True, False, False, False, False, False, False, False, False, False, False, False, False, True, False, False, False, False, False, False]

which when we check the number of circuit-hyperplanes, is exactly what we expected.

[frozenset(['c', 'b', 'e', 'd']), frozenset(['h', 'e', 'g', 'f'])]

You should let us see the code that you used that produced the incorrect answers, so we can tell whether it is a Sage bug, a sage.matroids bug, or user-error!

Finally, Stefan van Zwam has written a Mathematica program using Groebner bases to determine whether a matroid is representable, but the problem is hard unless you only want to know about matroids with less than 10 elements. I am not sure if he intends to add it to the Sage code-base or whether he even has it still. Ask him: https://www.math.lsu.edu/~svanzwam/programming.html

Answer 2

Here I only address your representation-of-a-matroid algorithm question.

The paper,

Massimiliano Lunelli, Antonio Laface. "Representation of matroids." 2002. (arXiv abs link).

uses Gröbner bases of polynomials over the ring of integers to decide if a given matroid is representable. Here is a quote describing some results of using their algorithm:

---

---

Their code is was available at Lunelli's website, as cited in their paper.