Subsets with hereditary property

[ncohen]

As discussed in ​https://groups.google.com/d/topic/sage-devel/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

[ncohen]

Here it is, at long last. I also removed the **kwds from SimplicialComplex, because I hate to see things like that work:

sage: SimplicialComplex(aergahgae="erharh")
Simplicial complex with vertex set () and facets {()}

It is the kind of things that makes you waste 30minutes over a typo in the function's input.

Nathann

[git]

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

​8fd05ec	trac #16994: Subsets with hereditary property
​0f49108	trac #16994: cleaner input for SimplicialComplex

[ncohen]

Anybody ?...

[dimpase]

I'm having a look now.

[dimpase]

there is is_mutable and is_immutable... shouldn't one of these go?

[ncohen]

there is is_mutable and is_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

[dimpase]

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)}

cf

sage: SimplicialComplex([(0, 4), (0, 1, 2), (0, 1, 3)])
Simplicial complex with vertex set (0, 1, 2, 3, 4) and facets {(0, 4), (0, 1, 2), (0, 1, 3)}

add vertices please... (e.g. take the union of facets)

[git]

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

​6f9ca0d

trac #16994: Bugfix

[dimpase]

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

[ncohen]

How about adding some real example?

Please add a commit if you want this example to be included.

Nathann

[dimpase]

New commits:

​2308e55

adding a hard example

[dimpase]

Otherwise LGTM. So you can flip this to positive review if you like my commit :-)

[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 built-in

I don't understand why, however O_o

Nathann

[ncohen]

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

[dimpase]

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 built-in

I 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

[git]

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

​ee38a01

'exists -> any', and some doc

[dimpase]

OK, done.

[ncohen]

Well.. Looks good, thanks :-)

Nathann

[ncohen]

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

[dimpase]

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).