Opened 5 years ago

Closed 5 years ago

#16994 closed enhancement (fixed)

Subsets with hereditary property

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.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/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

Change History (24)

comment:1 Changed 5 years ago by ncohen

  • 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

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

comment:2 Changed 5 years ago by ncohen

  • Cc jhpalmieri added

comment:3 Changed 5 years ago by git

  • Commit set to 0f491081d2d7cbd47029d02419e909cf0f50e865

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

8fd05ectrac #16994: Subsets with hereditary property
0f49108trac #16994: cleaner input for SimplicialComplex

comment:4 Changed 5 years ago by ncohen

Anybody ?...

comment:5 Changed 5 years ago by dimpase

I'm having a look now.

comment:6 follow-up: Changed 5 years ago by dimpase

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

comment:7 in reply to: ↑ 6 Changed 5 years ago by 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

Last edited 5 years ago by ncohen (previous) (diff)

comment:8 Changed 5 years ago by 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)

Last edited 5 years ago by dimpase (previous) (diff)

comment:9 Changed 5 years ago by dimpase

  • Status changed from needs_review to needs_work

comment:10 Changed 5 years ago by ncohen

  • Status changed from needs_work to needs_review

comment:11 Changed 5 years ago by git

  • Commit changed from 0f491081d2d7cbd47029d02419e909cf0f50e865 to 6f9ca0d6060acbf1091dda13abb30f7eee8ed8d3

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

6f9ca0dtrac #16994: Bugfix

comment:12 follow-up: Changed 5 years ago by 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

comment:13 in reply to: ↑ 12 Changed 5 years ago by ncohen

How about adding some real example?

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

Nathann

comment:14 Changed 5 years ago by dimpase

  • Branch changed from u/ncohen/16994 to u/dimpase/16994
  • Commit changed from 6f9ca0d6060acbf1091dda13abb30f7eee8ed8d3 to 2308e55bef1d72e7b983fb7abeb1170da2f2cccc

New commits:

2308e55adding a hard example

comment:15 Changed 5 years ago by dimpase

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

comment:16 follow-up: Changed 5 years ago by 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

comment:17 Changed 5 years ago by 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

comment:18 in reply to: ↑ 16 Changed 5 years ago by 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

comment:19 Changed 5 years ago by git

  • 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 5 years ago by dimpase

OK, done.

comment:21 Changed 5 years ago by ncohen

  • Reviewers set to Dima Pasechnik
  • Status changed from needs_review to positive_review

Well.. Looks good, thanks :-)

Nathann

comment:22 follow-up: Changed 5 years ago by 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

comment:23 in reply to: ↑ 22 Changed 5 years ago by 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).

comment:24 Changed 5 years ago by vbraun

  • Branch changed from u/dimpase/16994 to ee38a018b50c8c5c614ec2f0856c8962670b7ce4
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.