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: | sage-combinat |
---|---|---|---|
Priority: | major | Milestone: | sage-6.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 sage-5.11 to sage-5.12
comment:3 Changed 7 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:4 Changed 7 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:5 Changed 7 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:6 Changed 7 years ago by
What means rank symmetric? Is disjoint union of a 3-element chain and a 5-element 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 rank-symmetric (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 max-min.
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[-i-1] for i in range(len(L)/2))
But I do not know whether level sets are given for non-ranked 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 rank-symmetric? For now only connected graded posets seems to have clear definition of what is rank-symmetry.
comment:11 Changed 7 years ago by
I gave one possible general definition above. In that definition the poset you give wouldn't be rank-symmetric.
I personally haven't seen examples where rank-symmetry was considered for non-connected 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
Side-note 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 time-critical, then don't bother with those. Just write an explanation of what function does and give some examples and non-examples of rank-symmetric 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 sage-6.4 to sage-6.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 h-i-1
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