Opened 5 years ago

Closed 5 years ago

#19141 closed enhancement (fixed)

Poset documentation polishing: Boolean-valued properties

Reported by: jmantysalo Owned by:
Priority: minor Milestone: sage-6.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:

Description

Check documentation in functions like is_bounded(), is_ranked() and so on.

This continues the series started with #18925, #18941 and #18959.

Change History (29)

comment:1 Changed 5 years ago by jmantysalo

  • Branch set to u/jmantysalo/poset_documentation_polishing__boolean_valued_properties

comment:2 Changed 5 years ago by git

  • Commit set to d99ab5f27d400709e8108c41e3eb62623ac4f83a

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

d99ab5fPolishing to documentation of boolean-valued poset functions.

comment:3 Changed 5 years ago by jmantysalo

  • Cc kdilks added
  • Milestone changed from sage-wishlist to sage-6.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 jmantysalo

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

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 jmantysalo

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 4-colorable.

--

But for now this ticket is ready for review. Certificates can be think later.

comment:7 Changed 5 years ago by jmantysalo

  • Milestone changed from sage-6.9 to sage-6.10

comment:8 follow-up: Changed 5 years ago by kdilks

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 called is_totally_ordered, to avoid confusion with checking that a given subset of the poset forms a chain? Or maybe is_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 jmantysalo

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 called is_totally_ordered, to avoid confusion with checking that a given subset of the poset forms a chain? Or maybe is_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 git

  • Commit changed from d99ab5f27d400709e8108c41e3eb62623ac4f83a to 23c9b77b43ca19c73e49e7a5250c0e982b2859dc

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

23c9b77Modifications as suggested by kdilks.

comment:11 Changed 5 years ago by jmantysalo

Better? Should it be is_totally_ordered? I used is_total_order.

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

  • 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 for is_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 git

  • Commit changed from 23c9b77b43ca19c73e49e7a5250c0e982b2859dc to 39d1e185906821d6fcece65560e1081eb11e1493

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

39d1e18Back to is_chain. Was a bad idea.

comment:15 Changed 5 years ago by jmantysalo

  • Status changed from needs_work to needs_review

comment:16 follow-up: Changed 5 years ago by kdilks

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:

39d1e18Back to is_chain. Was a bad idea.
Last edited 5 years ago by kdilks (previous) (diff)

comment:17 in reply to: ↑ 12 Changed 5 years ago by kdilks

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 jmantysalo

Replying to kdilks:

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.

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 filter-out -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 jmantysalo

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

If you're working within Sage, going one step at a time, and have tab-completion 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 jmantysalo

Replying to kdilks:

If you're working within Sage, going one step at a time, and have tab-completion 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 jmantysalo

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

  • 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 non-ranked 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 ; follow-up: Changed 5 years ago by vdelecroix

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 method is_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
    ...
Last edited 5 years ago by vdelecroix (previous) (diff)

comment:25 in reply to: ↑ 24 Changed 5 years ago by jmantysalo

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 kdilks

But in this case, they really can be phrased as the exact same thing.

comment:27 Changed 5 years ago by vbraun

  • Status changed from positive_review to needs_work

Reviewer name missing

comment:28 Changed 5 years ago by kdilks

  • Reviewers set to Kevin Dilks
  • Status changed from needs_work to positive_review

comment:29 Changed 5 years ago by vbraun

  • Branch changed from u/jmantysalo/poset_documentation_polishing__boolean_valued_properties to 39d1e185906821d6fcece65560e1081eb11e1493
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.