possible bug in is_valid()

[Charles Wang]

Hi,

I was experimenting with sage-matroid and I constructed the matroid:

M=Matroid(groundset='1234',bases=['12','13','23','34'])
M.is_valid()
True

This should not be a valid matroid ('4' is an independent set, but it cannot be augmented to a larger independent set by any element of '12'), but M.is_valid() returns True in this case. Similarly, it seems there are non-matroids on 5 or more elements that also slip by is_valid(), though I haven't looked at any explicitly.

Could someone explain why this is happening? (or tell me that I need to update Sage: I am running Sage 6.9)

Thanks!

Charles

[Stefan van Zwam]

Hi Charles,

That’s definitely a bug. The problem is in the file BasisExchangeMatroid.pyx, line 2303. We are comparing pairs (X,Y) of bases, testing the exchange axiom. In that line we try to set the current basis (an internal variable) to Y. This may not work if the exchange axioms don’t hold, yet we don’t test for it. After line 2303 (which starts with self.__move), add:

                if not bitset_equal(self._current_basis, BB._subsets[pointerY]):

                    # We failed to set the current basis to Y through basis exchanges.

                    # Therefore, the exchange axioms are violated!

                    return False

I’ll open a Trac ticket to fix it formally in a moment.

Thank you so much for the report!

—Stefan.

--

---
You received this message because you are subscribed to the Google Groups "sage-matroid" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-matroid...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Stefan van Zwam]

Trac ticket (with positive review) here:

http://trac.sagemath.org/ticket/20172

Incidentally, it looks like that code has some room for a speed improvement, by setting self._current_basis to X in the outer loop. I can't think of a good reason for doing it the way it's done now... But I don't want to spend time on it myself.

[Charles Wang]

Hi Stefan,

Many thanks for the fix. Unfortunately when I try it myself I run into some errors:

sage/matroids/basis_exchange_matroid.pyx:2304:35: undeclared name not builtin: bitset_equal

sage/matroids/basis_exchange_matroid.pyx:2304:68: Cannot convert 'bitset_t' to Python object

What should I do to correct this?

Thanks!

Charles

[Stefan van Zwam]

Oops. It’s bitset_eq instead of bitset_equal.

Cheers,

Stefan.