Fwd: is_valid returns True for invalid matroid

[Dima Pasechnik]

On Tuesday, 3 March 2015 10:54:13 UTC, kfc79 wrote:

from sage.matroids.advanced import setprint
M=Matroid(groundset='abcdef',circuit_closures={1: ['ab'],4: ['abcde'],6: ['abcdef']})
setprint(M.circuits())
setprint(M.circuit_closures())
M
M.is_valid()

The set 'ab' is a circuit closure with rank 1, therefore it must be a parallel pair. This is confirmed by the fact that the only circuit of M is the set 'ab'.

The set 'abcdef' is defined as having rank 6 in the construction of the matroid, therefore it is an independent set. This is plainly contradictory; 'ab' and all its supersets are dependent, but 'abcdef' and all subsets are independent. So there is no matroid with the circuit closures and ranks given. Additionally, M can be seen to have rank 5 by the output of the fourth line. Again, this contradicts the construction.

But is_valid returns True.

Compare with

N=matroid(groundset='abcdef',circuits=['ab'])
setprint(N.circuits())
setprint(N.circuit_closures())
N.is_valid()

The matroid N returns the same set of circuits, but not the same circuit closures. As a matroid can be defined by either its circuits, or its circuit closures with their ranks, this is again a contradiction; at least one of M & N must not actually be a matroid.

Running Sage 6.4.1 on 64-bit Arch Linux, kernel version 3.17.3-1-ARCH. Intel Core i5-4670 quad-core processor. Compiled from source.

[Stefan van Zwam]

The problem arises because we check rank axioms in is_valid. The rank function computed from your M gives the following matroid:

N = Matroid(groundset='abcdef', rank_function=M.rank)
setprint(N.circuit_closures())
N.rank()

{1: {{'a', 'b'}}}
5

The solution to this issue is to check circuit-closure axioms instead in the CircuitClosuresMatroid class. It would probably still be possible to create a matroid based on an invalid set of circuits, which results in a valid set of circuit-closures, but unless we create a CircuitsMatroid I see no way around that.

M = Matroid(circuits=['ab', 'ac'])
setprint(M.circuit_closures())

{0: {{'a'}}}

Cheers,

Stefan.