Implement two matroid polytopes

[chapoton]

To a matroid one can associate two polytopes.

• one with bases as vertices
• one with indep. sets as vertices

The former is a facet of the latter.

Here is an implementation.

[chapoton]

New commits:

​641d76c

trac #18XXX two matroid polytopes

[vdelecroix]

Nice commit message ;-) You know that you can modify it afterwards by doing

git commit --amend

[vdelecroix]

Could you add a link to the published version of the article ​http://link.springer.com/article/10.1007%2Fs00454-008-9080-z (and keep the arXiv one)?

Isn't there any interesting feature of these polytopes that would be cool to have in the documentation? Right now you only show that you can construct them... not very fancy.

Code looks good otherwise.

Vincent

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​6484e71

trac #18183 more precise reference with doi

[chapoton]

Thanks for having a look.

I have added the publication data, and the doi

I have nothing fancy to add in the doctest, sorry.

If we had the Ehrhart polynomial, we could check that their coeffs are positive..

[vdelecroix]

Replying to chapoton:

Thanks for having a look.

I have added the publication data, and the doi

I have nothing fancy to add in the doctest, sorry.

If we had the Ehrhart polynomial, we could check that their coeffs are positive..

We do! This is in Latte (see #15180).

1. do sage -i latte_int

2. def latte_input_file(P, filename='/tmp/latte.in'):
       assert P.n_equations() == 0
       f = open(filename, 'w')
       f.write("{} {}\n".format(P.n_inequalities(), P.ambient_dim()+1))
       for l in P.inequality_generator():
           f.write(' '.join(map(str,l)))
           f.write('\n')
       f.close()
   

3. Then generate the file with the above code and run

    $ sage -sh
    $ count --ehrhart-polynomial /tmp/latte.in
    ...
    Ehrhart polynomial:  + 1 * t^0 + 3 * t^1 + 3 * t^2 + 1 * t^3
    $ exit
   

Would be really cool to have that properly interfaced within Sage!

Vincent

[ncohen]

Algorithmicaly it looks a bit weird to do something like that:

vertices = [ambient.sum(vector_e[convert[i]] for i in IS)
            for r in range(self.full_rank() + 1)
            for IS in self.independent_r_sets(r)]

You enumerate the 'r+1' independent sets without using the information you got from the sets of order 'r'.

I don't know if it can be useful here, but there is something *very* related in Sage:

​http://www.sagemath.org/doc/reference/combinat/sage/combinat/subsets_hereditary.html

Nathann

[chapoton]

Well, I see your point. The true problem is that there is no independent_sets method for matroids.

what do you mean about the ref ?

[ncohen]

Hellooooooooo,

Well, I see your point. The true problem is that there is no independent_sets method for matroids.

You can get one like that:

def independent_sets_iterator(M):
    from sage.combinat.subsets_hereditary import subsets_with_hereditary_property
    for x in subsets_with_hereditary_property(M.is_independent,M.groundset()):
        yield x

Disclaimers:

• It is a 'fake' iterator, i.e. the amount of memory it requires is far from constant. It does not store all bases at once, but you will store at some point the 'independent sets of size r or r+1' for every r

• I have no idea if the method is optimal algorithmically. It is meant to work for any 'hereditary' function (a property verified by Matroid.is_independent), and in particular does not use any property of matroids

• I suspect that it is asymptotically faster than what you do right now. The matroid algorithm to enumerate all independent sets of size 'r' is to try all 'r'-subset and run a is_independent test.

• This implementation is at a much higher level than the Matroid implementation: the matroid code works on bitsets, while subsets_with_hereditary_property works on lists of arbitrary objects. There is a (possibly big) loss of time there.

• There is a nice customization inside of subsets_with_hereditary_property, which is why I implemented this function: if it detects that {a,b,c} is not an independent set it will never try a superset of {a,b,c} again (this is achieved through some caching of the answers of the test function.

what do you mean about the ref ?

Oh sorry. I thought that it was a half-finishef entry, I had not noticed that you were only refering to another one (which is properly written).

Nathann

[chapoton]

It seems that the current branch is slightly faster..

sage: M=matroids.named_matroids.Q10()
sage: %timeit  P = M.independence_matroid_polytope()
10 loops, best of 3: 135 ms per loop

compared to the one using your iterator:

sage: M=matroids.named_matroids.Q10()
sage: %timeit  P = M.independence_matroid_polytope()
10 loops, best of 3: 143 ms per loop

So I propose to let to another ticket the work to have a proper independent_sets method.

[vdelecroix]

Hum. I did have a look at matroids independent_r_sets method. And the way to generate all independent set is to generate all sets and filter those which are independent... really!

res = []
for X in combinations(self.groundset(), r):
    X = frozenset(X)
    if self._rank(X) == len(X):
        res.append(X)
    return res

[ncohen]

This is the reason why I believe that the independent_sets_iterator I mentionned above will be asymptotically faster.

[vdelecroix]

This ticket is good to go!

I will try to implement something more serious for independent sets in matroids. The proposition of Nathann is not ideal since we do not want to store the "no sets" in the iteration. The boolean function is cheap in the present case.

[ncohen]

I will try to implement something more serious for independent sets in matroids. The proposition of Nathann is not ideal since we do not want to store the "no sets" in the iteration. The boolean function is cheap in the present case.

You do store them, but you store one bit for each of them. So it is not terribly large either. Why are you sure that the function is cheap in this case by the way?

Nathann

[ncohen]

err. Not 'one bit for each of them'. One bit for all inclusionwise minimal no-sets. Actually, I'd be ready to bet that storing all independent sets of size r is more expensive that that already.