5
$\begingroup$

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)

$\endgroup$

2 Answers 2

5
+100
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Thank you for the comprehensive answer. The code I used was essentially the same as yours, only that instead of ranging over nonbases, I was ranging over subsets thereof (also, sloppily, I was doing my manipulations with lists of sets instead of the native lists of frozensets for the matroids class). $\endgroup$ Dec 12, 2014 at 10:07
  • $\begingroup$ Incidentally, it is somehow odd to me that for all of the matroids I tried (Fano, Vamos, K_4, Pappus, NonPappus), all the "naive relaxations" adding some nonbases were actually matroids (I got the same outcome as you when I tried the matroid J). Is there any general reason why this is the case other than coincidence, or "Fano, Vamos, Pappus, K_4 have few nonbases"? $\endgroup$ Dec 12, 2014 at 10:13
  • $\begingroup$ I'll take your answer, but let me first reiterate my first question: do you know if the relaxations (aka weak preimages) of a matroid naturally show up in some context? (with apologies if that's mentioned in Matroid Theory's 2nd edition, since currently I have no access to it). $\endgroup$ Dec 12, 2014 at 10:17
  • $\begingroup$ You were unlucky in that for all three of those matroids, the set of circuit-hyperplanes happens to coincide with the set of nonbases. As for the first question, I don't know of any natural (non-matroidal) place where all relaxations of a given matroid are considered, though there are technical results about such things. $\endgroup$ Dec 15, 2014 at 8:05
0
$\begingroup$

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:


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

$\endgroup$
2
  • $\begingroup$ Thanks for the answer. Their algorithm is the same as the one in Theorem 6.8.9. in the second edition of Oxley's Matroid Theory, which is the one I had in mind while writing the question. Unfortunately, their code is nowhere to be found in Lunelli's website... $\endgroup$ Dec 11, 2014 at 13:20
  • $\begingroup$ @CamiloSarmiento: Yes, sorry, it appears he removed the directory cited in their paper (and I had a typo in the URL). Of course you could write him directly. $\endgroup$ Dec 11, 2014 at 13:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.