Opened 5 years ago
Closed 5 years ago
#19141 closed enhancement (fixed)
Poset documentation polishing: Booleanvalued properties
Reported by:  jmantysalo  Owned by:  

Priority:  minor  Milestone:  sage6.10 
Component:  combinatorics  Keywords:  poset 
Cc:  kdilks  Merged in:  
Authors:  Jori Mäntysalo  Reviewers:  Kevin Dilks 
Report Upstream:  N/A  Work issues:  
Branch:  39d1e18 (Commits)  Commit:  39d1e185906821d6fcece65560e1081eb11e1493 
Dependencies:  Stopgaps: 
Change History (29)
comment:1 Changed 5 years ago by
 Branch set to u/jmantysalo/poset_documentation_polishing__boolean_valued_properties
comment:2 Changed 5 years ago by
 Commit set to d99ab5f27d400709e8108c41e3eb62623ac4f83a
comment:3 Changed 5 years ago by
 Cc kdilks added
 Milestone changed from sagewishlist to sage6.9
 Status changed from new to needs_review
This contains one code change: is_chain()
for empty poset returns True
.
is_incomparable_chain_free
rejects argument 0
, as it makes no sense. Also I added "interval order" etc. for googlers. (Code could be changed from recursive to iterative. Or maybe just drop support for list type argument?)
Otherwise this is mostly polishing. I tried to explain intuitively what means for example to be ranked. Actually pictures would be good here.
I also added test for empty poset to all functions that I checked.
comment:4 Changed 5 years ago by
A question not relating to (only) documentation: How much we should have certificate
style options? For almost every Boolean valued function there can be one. For is_incomparable_chain_free
it is a pair of chains. For is_meet_semilattice
it is pair of elements without a meet. And so on.
For graphs we have for example is_eulerian
and eulerian_circuit
, and it feels logical to me.
comment:5 followup: ↓ 6 Changed 5 years ago by
I think that sounds like a good idea. It might require additional coding in some cases, since the best algorithm for determining true/false may not always involve finding such a certificate.
Would we want to have separate functions for returning just a boolean versus possibly returning a certificate like in that graph example, or would we just want to add an optional parameter certificate
to the existing function?
comment:6 in reply to: ↑ 5 Changed 5 years ago by
Replying to kdilks:
Would we want to have separate functions for returning just a boolean versus possibly returning a certificate like in that graph example, or would we just want to add an optional parameter
certificate
to the existing function?
I think that it depends on what mathematicians think. There is no mathematical definition for "mathematically interesting".
For a graph we have the chromatic number. We might also want to see an example of some coloring. Or maybe we want to count how many different coloring the graph has. Or make a list of them. Or maybe just check that the graph is not 4colorable.

But for now this ticket is ready for review. Certificates can be think later.
comment:7 Changed 5 years ago by
 Milestone changed from sage6.9 to sage6.10
comment:8 followup: ↓ 9 Changed 5 years ago by
Just writing down my comments as I read through, I may make some of the changes mentioned if I get a chance.
 In
is_incomparable_chain_free()
the three cases of (m+n)free having a special name, the case (1+2) is missing the parentheses around 1+2.
 I think the input for
is_incomparable_chain_free
is a bit confusing, since m can be an integer or a list of pairs of integers. Or at least the first part of the decription needs to be a bit more verbose to describe what's happening.
 I don't like the name
is_chain()
being used for checking if a poset is totally ordered. Shouldn't this be calledis_totally_ordered
, to avoid confusion with checking that a given subset of the poset forms a chain? Or maybeis_chain_poset()
?
 Maybe the definition of a poset being connected could mention that an equivalent definition is the Hasse diagram being connected?
 Informal definition of a ranked poset should be touched up a bit. Should say something more along the lines of 'all cover relations are between elements on adjacent levels'. Strictly speaking, saying they can't skip levels doesn't exclude the possibility of them being on the same level. I also think the 'formal definition' should come before the informal one, and not be branded as 'formal'.
 I'm not sure the informal definition of a graded poset helps at all. Saying all maximal chains have the same length is pretty clear. And if it does stay, there's one typo ('throught').
comment:9 in reply to: ↑ 8 Changed 5 years ago by
Replying to kdilks:
 I think the input for
is_incomparable_chain_free
is a bit confusing, since m can be an integer or a list of pairs of integers. Or at least the first part of the decription needs to be a bit more verbose to describe what's happening.
As I asked: "Or maybe just drop support for list type argument?". It is easy to guess why the list argument is done: to have slightly easier way to filter semiorders. But it is still oneliner to write without list type argument.
To drop it, to keep and clarify the documentation, or to deprecate it?
 I don't like the name
is_chain()
being used for checking if a poset is totally ordered. Shouldn't this be calledis_totally_ordered
, to avoid confusion with checking that a given subset of the poset forms a chain? Or maybeis_chain_poset()
?
Very true. Not is_chain_poset
, as it is too easy to confuse with is_chain_of_poset
. So, deprecation and a new name?
 Maybe the definition of a poset being connected could mention that an equivalent definition is the Hasse diagram being connected?
Yes. Actually it seems obvious from the name what the function does.
 Informal definition of a ranked poset should be touched up a bit. Should say something more along the lines of 'all cover relations are between elements on adjacent levels'. Strictly speaking, saying they can't skip levels doesn't exclude the possibility of them being on the same level. I also think the 'formal definition' should come before the informal one, and not be branded as 'formal'.
This is a function where formal definition is easy, but still very hard compared to informal definition  or to a picture. But yes, I must think the wording.
 I'm not sure the informal definition of a graded poset helps at all. Saying all maximal chains have the same length is pretty clear. And if it does stay, there's one typo ('throught').
Yeah, maybe I remove it.
comment:10 Changed 5 years ago by
 Commit changed from d99ab5f27d400709e8108c41e3eb62623ac4f83a to 23c9b77b43ca19c73e49e7a5250c0e982b2859dc
Branch pushed to git repo; I updated commit sha1. New commits:
23c9b77  Modifications as suggested by kdilks.

comment:11 Changed 5 years ago by
Better? Should it be is_totally_ordered
? I used is_total_order
.
comment:12 followups: ↓ 13 ↓ 17 Changed 5 years ago by
chain is standard terminology for poset. Why would you want to remove it? Instead I suggest to make is_totally_ordered
as an alias for is_chain
. Moreover there is the notion of antichain that does not have a anti totally ordered counterpart.
comment:13 in reply to: ↑ 12 Changed 5 years ago by
 Status changed from needs_review to needs_work
Replying to vdelecroix:
chain is standard terminology for poset. Why would you want to remove it? Instead I suggest to make
is_totally_ordered
as an alias foris_chain
. Moreover there is the notion of antichain that does not have a anti totally ordered counterpart.
True, antiordered does not sound good.
So I guess I will revert this change. The reason was possible confusion of a set being a chain of poset and a whole poset being a chain.
comment:14 Changed 5 years ago by
 Commit changed from 23c9b77b43ca19c73e49e7a5250c0e982b2859dc to 39d1e185906821d6fcece65560e1081eb11e1493
Branch pushed to git repo; I updated commit sha1. New commits:
39d1e18  Back to is_chain. Was a bad idea.

comment:15 Changed 5 years ago by
 Status changed from needs_work to needs_review
comment:16 followup: ↓ 18 Changed 5 years ago by
I know that 'chain' is standard terminology for a totally ordered poset, but it seems unnecessarily confusing to have is_chain()
and is_chain_of_poset()
floating around. Especially since is_chain_of_poset()
is much more likely to be used, and has the harder to find/guess name.
Why not just have one function called is_chain()
that does what is_chain_of_poset()
currently does? If you want to want to find out if you entire poset is a chain, you can run is_chain(P.elements())
. Or even is_isomorphic(Posets.ChainPoset(len(P.elements()))
. There aren't special aliases for determining isomorphism type with any other family of posets.
New commits:
39d1e18  Back to is_chain. Was a bad idea.

comment:17 in reply to: ↑ 12 Changed 5 years ago by
Replying to vdelecroix:
Moreover there is the notion of antichain that does not have a anti totally ordered counterpart.
If we were to include an alias for checking this (which I don't think we should), it would be 'totally incomparable'.
comment:18 in reply to: ↑ 16 Changed 5 years ago by
Replying to kdilks:
Why not just have one function called
is_chain()
that does whatis_chain_of_poset()
currently does? If you want to want to find out if you entire poset is a chain, you can runis_chain(P.elements())
. Or evenis_isomorphic(Posets.ChainPoset(len(P.elements()))
. There aren't special aliases for determining isomorphism type with any other family of posets.
I have used is_chain
to find some interesting examples, i.e. to filter out uninteresting cases. Fortunately is_chain
does not take arguments, and is_chain_of_poset
has a mandatory argument. Hence the error will be easily seen.
I guess there could also be is_antichain()
, as it can too be useful as filterout function.
(And I would not mind having something like describe
, like in small group id database has for groups. It could output something like "Vertical decomposition of Boolean lattice 3 and Tamari lattice 4." But might not be that easy to make it...)
comment:19 Changed 5 years ago by
Btw, I keep this as needs_review. That's because more changes can be made later. Real question for review is "Does this patch make Sage better?"
comment:20 followup: ↓ 21 Changed 5 years ago by
If you're working within Sage, going one step at a time, and have tabcompletion at your disposal, then the error will be easily seen. If you're writing more complex code or are developing the source code, then it's not clear. This isn't just a theoretical concern, this is a problem I personally run into pretty much every time I've worked with posets.
comment:21 in reply to: ↑ 20 Changed 5 years ago by
Replying to kdilks:
If you're working within Sage, going one step at a time, and have tabcompletion at your disposal, then the error will be easily seen. If you're writing more complex code or are developing the source code, then it's not clear. This isn't just a theoretical concern, this is a problem I personally run into pretty much every time I've worked with posets.
But you will get an error message as soon as the code comes to is_chain(something)
or is_chain_of_poset()
.
comment:22 Changed 5 years ago by
Btw, should is_slender
be like it now is? For comparison, is_rank_symmetric
raises an error if the poset is not of assumed type.
comment:23 followup: ↓ 24 Changed 5 years ago by
 Status changed from needs_review to positive_review
My main point is that I really think is_chain()
should be the method that checks if a given set is a chain of the poset. Maybe we could rename the other method is_chain_poset()
? But maybe that can be a separate ticket, I'll set positive review for the changes made here.
I think it's fine the way that it is. For is_rank_symmetric()
, we have a separate category of ranked posets for it to be a method on, and the question doesn't really make sense for a nonranked poset. With is_slender()
, I don't think we have a category framework for graded/bounded posets. Also, the question of whether a poset has an interval of rank 2 with more than 4 elements may be of interest independent of the assumption that it's graded/bounded, and it's easy enough to add your own checks with is_bounded()
and is_graded()
if you really want to make it necessary. Maybe the right compromise would be to add optional parameters bounded
and graded
that can be set depending on whether you feel like imposing those conditions or not.
comment:24 in reply to: ↑ 23 ; followup: ↓ 25 Changed 5 years ago by
Replying to kdilks:
My main point is that I really think
is_chain()
should be the method that checks if a given set is a chain of the poset. Maybe we could rename the other methodis_chain_poset()
? But maybe that can be a separate ticket, I'll set positive review for the changes made here.
You can have both
def is_chain(self, data=None): r""" Test whether a given subset of elements is a chain. By default, does the test for all the elements of the poset. """ if data is None: data = self ...
comment:25 in reply to: ↑ 24 Changed 5 years ago by
Replying to vdelecroix:
You can have both
def is_chain(self, data=None):
No! Please no!
They do very much different thing. Already rank
gives me a headache, as it can return a property of a poset (height, not depending if the poset is ranked or not) or a a property of an element (rank in ranked poset).
...or at least this is how I see it. A poset is an abstract thing that might have a property like width. Or it is a concrete thing where I can ask for example if a
is greater than b
. But if majority sees it other way, then of course I must accommodate to it.
comment:26 Changed 5 years ago by
But in this case, they really can be phrased as the exact same thing.
comment:27 Changed 5 years ago by
 Status changed from positive_review to needs_work
Reviewer name missing
comment:28 Changed 5 years ago by
 Reviewers set to Kevin Dilks
 Status changed from needs_work to positive_review
comment:29 Changed 5 years ago by
 Branch changed from u/jmantysalo/poset_documentation_polishing__boolean_valued_properties to 39d1e185906821d6fcece65560e1081eb11e1493
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
Polishing to documentation of booleanvalued poset functions.