Posets package: Bug in rankFunction method

[bbarwick]

A poset P is ranked if there exists an integer-valued function r : V(P) -> ZZ such that

1. The function r respects the partial order (i.e., if u < v, then r(u) < r(v)).
2. If v covers u, then r(v) = r(u)+1.

The following example demonstrates a bug in the Posets package in which the rank function returned by rankFunction violates part 2 of the definition above.

i18 : P = poset({3, 4, 5, 6, 7, 8, 9, 10, 11},{{4, 7}, {4, 8}, {5, 11}, {5, 9}, {6, 4}, {6, 9}, {7, 3}, {8, 3}, {9, 7}, {9, 8}, {10, 5}, {11, 4}})

o18 = P

o18 : Poset

i19 : isRanked P

o19 = true

i20 : vertices P

o20 = {3, 4, 5, 6, 7, 8, 9, 10, 11}

o20 : List

i21 : rankFunction P -- Notice that 6 and 9 both have rank 2.

o21 = {5, 3, 1, 2, 4, 4, 2, 0, 2}

o21 : List

i22 : coveringRelations P -- But 9 covers 6.

o22 = {{4, 7}, {4, 8}, {5, 11}, {5, 9}, {6, 4}, {6, 9}, {7, 3}, {8, 3}, {9, 7}, {9, 8}, {10, 5}, {11, 4}}

o22 : List

[DanGrayson]

@dcookii -- who should be looking at this?

[ghost]

{Name => "Sonja Mapes", Email => "smapes1@nd.edu"} or {Name => "Gwyn Whieldon", Email => "whieldon@hood.edu"}

On Thu, May 24, 2018 at 2:34 PM, Daniel R. Grayson <notifications@github.com

wrote:

@dcookii https://github.com/dcookii -- who should be looking at this?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/Macaulay2/M2/issues/787#issuecomment-391816293, or mute the thread https://github.com/notifications/unsubscribe-auth/AE4lW45rqH5NGtbJshFkhniJ9K1abgWRks5t1v0_gaJpZM4ULcpg .

[bbarwick]

Here is a slightly simpler example to demonstrate the bug using less vertices and such that the vertex labels correspond to their indices. The isRanked method returns that this poset is ranked, but it actually isn't (this is easy to see since it has maximal chains of different lengths).

i2 : P = poset({0,1,2,3,4},{{0,2},{2,3},{1,4},{0,4},{1,3}}) o2 = P

o2 : Poset i3 : isRanked P o3 = true

i4 : vertices P o4 = {0, 1, 2, 3, 4} o4 : List

i5 : rankFunction P -- Notice that 1 and 4 both have rank 1. o5 = {0, 1, 1, 2, 1} o5 : List

i6 : coveringRelations P -- But 4 covers 1. o6 = {{0, 4}, {0, 2}, {1, 4}, {1, 3}, {2, 3}} o6 : List

I've had a little time to look at the rankFunction method in Posets.m2 and compare it to the corresponding method ranked from the Maple Posets package (http://www.math.lsa.umich.edu/~jrs/software/posets2.4v.txt), and while the implementations are very similar, there is one key spot where the methods differ. A direct port of the ranked method from the Maple package would look like:

rankFunction = method() rankFunction Poset := List => P -> ( if P.cache.?rankFunction then return P.cache.rankFunction; rk := apply(#P.GroundSet, i -> {i, 0}); if not P.cache.?coveringRelations then coveringRelations P; for r in P.cache.coveringRelations do ( tmp := last rk#(r#1) - last rk#(r#0) - 1; if tmp == 0 then continue; u := first rk#(r#0); v := first rk#(r#1); if u == v then ( if tmp == 0 then continue else return P.cache.rankFunction = null; ); if u == v then return P.cache.rankFunction = null; rk = if tmp > 0 then apply(rk, g -> if first g == u then {v, last g + tmp} else g) else apply(rk, g -> if first g == v then {u, last g - tmp} else g); ); P.cache.rankFunction = last \ rk )

The strikethrough lines should be deleted and the bold line should be added.

[DanGrayson]

@smapes @gwynwhieldon