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:

Status badges

Description

This patch implements a test for ranked posets if it is symmetric in ranks.

Attachments (1)

trac_14003-is_rank_symmetric-cs.patch (928 bytes) - added by stumpc5 8 years ago.

Download all attachments as: .zip

Change History (28)

Changed 8 years ago by stumpc5

comment:1 Changed 8 years ago by chapoton

please add doctests

comment:2 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:3 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:4 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:5 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:6 Changed 7 years ago by jmantysalo

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 stumpc5

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 jmantysalo

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 stumpc5

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 jmantysalo

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 stumpc5

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 jmantysalo

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 jmantysalo

  • Authors changed from Christian Stump to Jori Mäntysalo
  • 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

Intentionally left away from index of functions to prevent clashes. There is time until 6.9.


New commits:

cfbc7daFaster is_lattice().
83d1071Added is_rank_symmetric().

comment:14 Changed 6 years ago by git

  • Commit changed from 83d107157feb9f8598615aeeb4759a2899444a36 to 60bb536a1319266c8315c957fea52cb60283a34a

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

60bb536An error with git.

comment:15 Changed 6 years ago by jmantysalo

  • Status changed from needs_review to needs_work
Last edited 6 years ago by jmantysalo (previous) (diff)

comment:16 Changed 6 years ago by git

  • Commit changed from 60bb536a1319266c8315c957fea52cb60283a34a to a44e4247bce02518d4eb9100c3c2bb4c0f1e2379

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

a44e424Added a is_rank_symmetric() function.

comment:17 Changed 6 years ago by jmantysalo

  • Status changed from needs_work to needs_review

Now it should be OK. Sorry for the noise.

comment:18 Changed 6 years ago by jmantysalo

Christian, as I wrote the code from scratch, you can be the reviewer if you want.

comment:19 Changed 6 years ago by jmantysalo

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 chapoton

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)

Last edited 6 years ago by chapoton (previous) (diff)

comment:21 Changed 6 years ago by git

  • Commit changed from a44e4247bce02518d4eb9100c3c2bb4c0f1e2379 to 3cd7548d5ae45d1b3d26621b937591cdb0dc1926

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

3cd7548Reviewer comments fixed.

comment:22 Changed 6 years ago by jmantysalo

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.

Last edited 6 years ago by jmantysalo (previous) (diff)

comment:23 Changed 6 years ago by chapoton

  • Status changed from needs_review to positive_review

ok, good enough.

comment:24 Changed 6 years ago by jmantysalo

Thanks!

comment:25 Changed 6 years ago by vbraun

  • Status changed from positive_review to needs_work

Reviewer name is missing

comment:26 Changed 6 years ago by chapoton

  • 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 vbraun

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