Opened 6 years ago
Closed 6 years ago
#16994 closed enhancement (fixed)
Subsets with hereditary property
Reported by:  ncohen  Owned by:  

Priority:  major  Milestone:  sage6.4 
Component:  combinatorics  Keywords:  
Cc:  vinceknight, kcrisman, dimpase, jdemeyer, nthiery, vdelecroix, jhpalmieri  Merged in:  
Authors:  Nathann Cohen  Reviewers:  Dima Pasechnik 
Report Upstream:  N/A  Work issues:  
Branch:  ee38a01 (Commits)  Commit:  ee38a018b50c8c5c614ec2f0856c8962670b7ce4 
Dependencies:  Stopgaps: 
Description
As discussed in https://groups.google.com/d/topic/sagedevel/os1LzBjsYnQ/discussion, here is a ticket to implement a function that returns, given a boolean monotone function f
on the subsets of a set X
, all subsets S
of X
such that f(S)
is True.
The implementation assumes that f
is very costly to evaluate, and so caches as much as possible. It can also compute in parallel.
Nathann
Change History (24)
comment:1 Changed 6 years ago by
 Branch set to u/ncohen/16994
 Cc vinceknight kcrisman dimpase jdemeyer nthiery vdelecroix added
 Status changed from new to needs_review
 Summary changed from Simplicial Complex from boolean function to Subsets with hereditary property
comment:2 Changed 6 years ago by
 Cc jhpalmieri added
comment:3 Changed 6 years ago by
 Commit set to 0f491081d2d7cbd47029d02419e909cf0f50e865
comment:4 Changed 6 years ago by
Anybody ?...
comment:5 Changed 6 years ago by
I'm having a look now.
comment:6 followup: ↓ 7 Changed 6 years ago by
there is is_mutable
and is_immutable
... shouldn't one of these go?
comment:7 in reply to: ↑ 6 Changed 6 years ago by
there is
is_mutable
andis_immutable
... shouldn't one of these go?
These days I try to keep the amount of wars I start to a minimum.
I also want to stop fighting other people on their own grounds. I noticed that it decreased my chances of actually achieving anything, even when I am right.
Nathann
comment:8 Changed 6 years ago by
No vertices?!
sage: SimplicialComplex(from_characteristic_function=(lambda x:sum(x)<=4,range(5))) Simplicial complex with vertex set () and facets {(0, 4), (0, 1, 2), (0, 1, 3)}
comment:9 Changed 6 years ago by
 Status changed from needs_review to needs_work
comment:10 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:11 Changed 6 years ago by
 Commit changed from 0f491081d2d7cbd47029d02419e909cf0f50e865 to 6f9ca0d6060acbf1091dda13abb30f7eee8ed8d3
Branch pushed to git repo; I updated commit sha1. New commits:
6f9ca0d  trac #16994: Bugfix

comment:12 followup: ↓ 13 Changed 6 years ago by
How about adding some real example? E.g. I tested that the output (the famous 168 hyperovals in PG(2,4)) is correct on the following:
sage: l=map(Set,ProjectiveGeometryDesign(2,1,GF(4,name='a')).blocks()) sage: SimplicialComplex(from_characteristic_function=(lambda S: not exists(l, lambda x: Set(S).intersection(x).cardinality()>2)[0],range(21))) Simplicial complex with 21 vertices and 168 facets
takes 8 seconds on my desktop, so should be marked # long time
comment:13 in reply to: ↑ 12 Changed 6 years ago by
How about adding some real example?
Please add a commit if you want this example to be included.
Nathann
comment:14 Changed 6 years ago by
 Branch changed from u/ncohen/16994 to u/dimpase/16994
 Commit changed from 6f9ca0d6060acbf1091dda13abb30f7eee8ed8d3 to 2308e55bef1d72e7b983fb7abeb1170da2f2cccc
New commits:
2308e55  adding a hard example

comment:15 Changed 6 years ago by
Otherwise LGTM. So you can flip this to positive review if you like my commit :)
comment:16 followup: ↓ 18 Changed 6 years ago by
I was wondering what was the difference between "any" and "exists" and I found that in the docstring of "exists":
Note that this function is NOT suitable to be used in an if statement or in any place where a boolean expression is expected. For those situations, use the Python builtin
I don't understand why, however O_o
Nathann
comment:17 Changed 6 years ago by
Also, there was a text just before my example that talked about sets whose sum is smaller than 4. Could you add some other text before yours ?
Nathann
comment:18 in reply to: ↑ 16 Changed 6 years ago by
Replying to ncohen:
I was wondering what was the difference between "any" and "exists" and I found that in the docstring of "exists":
Note that this function is NOT suitable to be used in an if statement or in any place where a boolean expression is expected. For those situations, use the Python builtinI don't understand why, however
O_o
Ah, I see  that's cause exists returns a pair! (notice [0]
I had to put in).
OK, I'll fix this. Just a second
comment:19 Changed 6 years ago by
 Commit changed from 2308e55bef1d72e7b983fb7abeb1170da2f2cccc to ee38a018b50c8c5c614ec2f0856c8962670b7ce4
Branch pushed to git repo; I updated commit sha1. New commits:
ee38a01  'exists > any', and some doc

comment:20 Changed 6 years ago by
OK, done.
comment:21 Changed 6 years ago by
 Reviewers set to Dima Pasechnik
 Status changed from needs_review to positive_review
Well.. Looks good, thanks :)
Nathann
comment:22 followup: ↓ 23 Changed 6 years ago by
Hmmm... Funny. Your simplicial complex is a (21,6,12)
BIBD. And not one that we already have in the database.
sage: l=map(Set, designs.ProjectiveGeometryDesign(2,1,GF(4,name='a'))) sage: S=SimplicialComplex(from_characteristic_function=(lambda S: not any(Set(S).intersection(x).cardinality()>2 for x in l), range(21))) # long time sage: IS=IncidenceStructure([list(x) for x in s.maximal_faces()]) sage: IS.is_t_design(return_parameters=True) (True, (2, 21, 6, 12)) sage: (21,6,12) in sage.combinat.designs.database.DF False
I mean: currently the BIBD constructor does not even accept a lambda
parameter, but we could have had a difference family for it.
sage: (0,9,10,12,16,13,18,11,7,8,1,4,5,3,2,15,19,6,14,20,17) in IS.automorphism_group() True
And it turns out that there is a cyclic automorphism acting on the hypergraph, so there IS such a difference family.
Hmmmm....
Nathann
comment:23 in reply to: ↑ 22 Changed 6 years ago by
Replying to ncohen:
Hmmm... Funny. Your simplicial complex is a
(21,6,12)
BIBD.
this is not too surprising: these are the 168 octads containing a pair from a given triple of points in the famous Steiner system S(5,8,24) on 24 points.
And it turns out that there is a cyclic automorphism acting on the hypergraph, so there IS such a difference family.
yep, there got to be lots of such automorphisms (the full group of automorphisms is quite big).
comment:24 Changed 6 years ago by
 Branch changed from u/dimpase/16994 to ee38a018b50c8c5c614ec2f0856c8962670b7ce4
 Resolution set to fixed
 Status changed from positive_review to closed
Here it is, at long last. I also removed the
**kwds
fromSimplicialComplex
, because I hate to see things like that work:It is the kind of things that makes you waste 30minutes over a typo in the function's input.
Nathann