Implementation of a rank symmetric test for posets

[stumpc5]

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

[chapoton]

please add doctests

[jmantysalo]

What means rank symmetric? Is disjoint union of a 3-element chain and a 5-element chain symmetric?

[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

[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.

[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...

[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.

[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.)

[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.")

[jmantysalo]

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

---

New commits:

​cfbc7da	Faster is_lattice().
​83d1071	Added is_rank_symmetric().

[git]

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

​60bb536

An error with git.

[git]

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

​a44e424

Added a is_rank_symmetric() function.

[jmantysalo]

Now it should be OK. Sorry for the noise.

[jmantysalo]

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

[jmantysalo]

Ping...? I have a bunch of tickets waiting review. This one should not have anything special to think about.

[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)

[git]

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

​3cd7548

Reviewer comments fixed.

[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.

[chapoton]

ok, good enough.

[jmantysalo]

Thanks!

[vbraun]

Reviewer name is missing

[chapoton]

raah, sorry again..