Opened 7 years ago
Closed 7 years ago
#18183 closed enhancement (fixed)
Implement two matroid polytopes
Reported by:  chapoton  Owned by:  

Priority:  major  Milestone:  sage6.7 
Component:  matroid theory  Keywords:  matroid polytope 
Cc:  Merged in:  
Authors:  Frédéric Chapoton  Reviewers:  Vincent Delecroix 
Report Upstream:  N/A  Work issues:  documentation 
Branch:  6484e71 (Commits, GitHub, GitLab)  Commit:  6484e7198d41b716f4cb70dcf56ea7d849a6ce90 
Dependencies:  Stopgaps: 
Description
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.
Change History (18)
comment:1 Changed 7 years ago by
 Branch set to u/chapoton/18183
 Commit set to 641d76c39dfa5619c1b8759c52d855be2a917088
 Status changed from new to needs_review
comment:2 Changed 7 years ago by
Nice commit message ;) You know that you can modify it afterwards by doing
git commit amend
comment:3 Changed 7 years ago by
Could you add a link to the published version of the article http://link.springer.com/article/10.1007%2Fs004540089080z (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
comment:4 Changed 7 years ago by
 Status changed from needs_review to needs_work
 Work issues set to documentation
comment:5 Changed 7 years ago by
 Commit changed from 641d76c39dfa5619c1b8759c52d855be2a917088 to 6484e7198d41b716f4cb70dcf56ea7d849a6ce90
Branch pushed to git repo; I updated commit sha1. New commits:
6484e71  trac #18183 more precise reference with doi

comment:6 followup: ↓ 7 Changed 7 years ago by
 Status changed from needs_work to needs_review
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..
comment:7 in reply to: ↑ 6 Changed 7 years ago by
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).
 do
sage i latte_int

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()
 Then generate the file with the above code and run
$ sage sh $ count ehrhartpolynomial /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
comment:8 Changed 7 years ago by
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
P.S.:
+ REFERENCE: + + [DLHK2007]_
comment:9 followup: ↓ 10 Changed 7 years ago by
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 ?
comment:10 in reply to: ↑ 9 Changed 7 years ago by
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 halffinishef entry, I had not noticed that you were only refering to another one (which is properly written).
Nathann
comment:11 Changed 7 years ago by
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.
comment:12 Changed 7 years ago by
 Milestone changed from sage6.6 to sage6.7
comment:13 Changed 7 years ago by
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
comment:14 Changed 7 years ago by
This is the reason why I believe that the independent_sets_iterator
I mentionned above will be asymptotically faster.
comment:15 followup: ↓ 16 Changed 7 years ago by
 Reviewers set to Vincent Delecroix
 Status changed from needs_review to positive_review
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.
comment:16 in reply to: ↑ 15 Changed 7 years ago by
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
comment:17 Changed 7 years ago by
err. Not 'one bit for each of them'. One bit for all inclusionwise minimal nosets. Actually, I'd be ready to bet that storing all independent sets of size r is more expensive that that already.
comment:18 Changed 7 years ago by
 Branch changed from u/chapoton/18183 to 6484e7198d41b716f4cb70dcf56ea7d849a6ce90
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
trac #18XXX two matroid polytopes