Opened 8 years ago
Closed 6 years ago
#14003 closed enhancement (fixed)
Implementation of a rank symmetric test for posets
Reported by:  stumpc5  Owned by:  sagecombinat 

Priority:  major  Milestone:  sage6.9 
Component:  combinatorics  Keywords:  posets 
Cc:  chapoton  Merged in:  
Authors:  Jori Mäntysalo  Reviewers:  Frédéric Chapoton 
Report Upstream:  N/A  Work issues:  
Branch:  3cd7548 (Commits, GitHub, GitLab)  Commit:  3cd7548d5ae45d1b3d26621b937591cdb0dc1926 
Dependencies:  Stopgaps: 
Description
This patch implements a test for ranked posets if it is symmetric in ranks.
Attachments (1)
Change History (28)
Changed 8 years ago by
comment:1 Changed 8 years ago by
comment:2 Changed 8 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:3 Changed 7 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:4 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:5 Changed 7 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:6 Changed 7 years ago by
What means rank symmetric? Is disjoint union of a 3element chain and a 5element chain symmetric?
comment:7 Changed 7 years ago by
Currently, it is only implemented for ranked posets. This is, for posets admitting a rank function that is 0 on minimal elements and an upwards cover relations increases the rank by 1.
More generally, one can define more generally the rank of an element in a poset to be the distance (in the graph sense of the Hasse diagram) to a minimal element. For this, every element should be supposed to have finite distance. In ranked posets, this is equivalent to the above definition.
Either way, your disjoint union of two chains of different lengths is therefore not ranksymmetric (the rank sizes are 2,2,...,2,1,...,1 with the number of 2's being the minimal of the two lengths, and the number of 1's being maxmin.
I'd (obviously) be happy if you would take over this ticket!
Thanks, Christian
comment:8 Changed 7 years ago by
I am worried about how this should be defined. One possible definition is that L=[len(x) for x in P.level_sets()]
equals to [len(x) for x in P.dual().level_sets()]
. Another is that L
equals to reversed(L)
.
Coding errors are in a sense easy to fix, like giving correct answer. Wrong definition is like asking wrong question.
comment:9 Changed 7 years ago by
See the attached patch above, which is basically
L = [len(x) for x in P.level_sets()]
return all( L[i] == L[i1] for i in range(len(L)/2))
But I do not know whether level sets are given for nonranked posets...
comment:10 Changed 7 years ago by
Level sets are defined on every poset, or actually on every acyclic digraph.
But still I don't know what is wanted. For example Poset({0:[1,2], 1:[3], 3:[4], 4:[5], 6:[5]})
is ranked, is it ranksymmetric? For now only connected graded posets seems to have clear definition of what is ranksymmetry.
comment:11 Changed 7 years ago by
I gave one possible general definition above. In that definition the poset you give wouldn't be ranksymmetric.
I personally haven't seen examples where ranksymmetry was considered for nonconnected graded posets, and would be totally fine with having it defined only for those. (Btw: at some point we agreed that graded means that all maximal chains have the same length while ranked is given as defined above.)
comment:12 Changed 7 years ago by
Sidenote about graded vs. ranked: #16998.
You seems to already have working code. There is of course also many other ways to do it, for example to start with
L=P._hasse_diagram._rank_dict.values() D=dict((i, L.count(i)) for i in L)
and so on. But if you do not know this to be timecritical, then don't bother with those. Just write an explanation of what function does and give some examples and nonexamples of ranksymmetric poset. They are the hardest part with functions like this.
When then function is only defined to some specific type of posets, it should start with
if not self.is_graded() or not self.is_connected(): raise ValueError("Rank symmetry is only defined for connected graded posets.")
comment:13 Changed 6 years ago by
 Branch set to u/jmantysalo/rank_symmetric
 Commit set to 83d107157feb9f8598615aeeb4759a2899444a36
 Milestone changed from sage6.4 to sage6.9
 Status changed from new to needs_review
comment:14 Changed 6 years ago by
 Commit changed from 83d107157feb9f8598615aeeb4759a2899444a36 to 60bb536a1319266c8315c957fea52cb60283a34a
Branch pushed to git repo; I updated commit sha1. New commits:
60bb536  An error with git.

comment:15 Changed 6 years ago by
 Status changed from needs_review to needs_work
comment:16 Changed 6 years ago by
 Commit changed from 60bb536a1319266c8315c957fea52cb60283a34a to a44e4247bce02518d4eb9100c3c2bb4c0f1e2379
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
a44e424  Added a is_rank_symmetric() function.

comment:17 Changed 6 years ago by
 Status changed from needs_work to needs_review
Now it should be OK. Sorry for the noise.
comment:18 Changed 6 years ago by
Christian, as I wrote the code from scratch, you can be the reviewer if you want.
comment:19 Changed 6 years ago by
Ping...? I have a bunch of tickets waiting review. This one should not have anything special to think about.
comment:20 Changed 6 years ago by
1) in the raise statements, I would replace
the poset is assumed to be connected
by
the poset is not connected
and same for graded condition
2) the doc is not consistent with the code, symmetry should be between i and hi1
3) please use backticks instead of $
4) do not compute twice len(levels)
comment:21 Changed 6 years ago by
 Commit changed from a44e4247bce02518d4eb9100c3c2bb4c0f1e2379 to 3cd7548d5ae45d1b3d26621b937591cdb0dc1926
Branch pushed to git repo; I updated commit sha1. New commits:
3cd7548  Reviewer comments fixed.

comment:22 Changed 6 years ago by
Thanks Frédéric! These are now corrected. I also added the function to index of functions and added a test for the empty poset.
comment:23 Changed 6 years ago by
 Status changed from needs_review to positive_review
ok, good enough.
comment:24 Changed 6 years ago by
Thanks!
comment:25 Changed 6 years ago by
 Status changed from positive_review to needs_work
Reviewer name is missing
comment:26 Changed 6 years ago by
 Reviewers set to Frédéric Chapoton
 Status changed from needs_work to positive_review
raah, sorry again..
comment:27 Changed 6 years ago by
 Branch changed from u/jmantysalo/rank_symmetric to 3cd7548d5ae45d1b3d26621b937591cdb0dc1926
 Resolution set to fixed
 Status changed from positive_review to closed
please add doctests