Identifier
Mp00000: Permutations Weak order rowmotionPermutations
Name
Weak order rowmotion
Description
Any semidistributive lattice $L$ has a canonical labeling of the edges of its Hasse diagram by its join irreducible elements (see [1] and [2]). Rowmotion on this lattice is the bijection which takes an element $x \in L$ with a given set of down-labels to the unique element $y \in L$ which has that set as its up-labels (see [2] and [3]). For example, if the lattice is the distributive lattice $J(P)$ of order ideals of a finite poset $P$, then this reduces to ordinary rowmotion on the order ideals of $P$.
The weak order (a.k.a. permutohedral order) on the permutations in $S_n$ is a semidistributive lattice. In this way, we obtain an action of rowmotion on the set of permutations in $S_n$. Not much is known about the dynamics of weak order rowmotion, which seems unpredictable. One nontrivial collection of homomesies is described in Corollary 6.14 of [4].
References
[1] Reading, N. Noncrossing Arc Diagrams and Canonical Join Representations DOI:10.1137/140972391 arXiv:1405.6904
[2] Barnard, E. The Canonical Join Complex DOI:10.37236/7866 arXiv:1610.05137
[3] Thomas, H., Williams, N. Rowmotion in slow motion DOI:10.1112/plms.12251 arXiv:1712.10123
[4] Hopkins, S. The CDE property for skew vexillary permutations DOI:10.1016/j.jcta.2019.06.005 arXiv:1811.02404
[5] Defant, C., Williams, N. Semidistrim Lattices DOI:10.1017/fms.2023.46 arXiv:2111.08122
Sage code
#note that everything here is dualized (we use dual order and take joins of upper labels)
@cached_function
def dual_weak_order(n):
    f = lambda p,q : q.permutohedron_lequal(p)
    P = LatticePoset(Poset((Permutations(n), f)))
    ji = P.join_irreducibles()
    bot = P.minimal_elements()[0]
    return (P,ji,bot)

def upper_labels(P,ji,u):
    ul = []
    for v in P.upper_covers(u):
        cur_min = None
        for j in ji:
            if P.le(j,v) and not(P.le(j,u)) and (cur_min == None or P.le(j,cur_min)):
                cur_min = j
        ul.append(cur_min)
    return ul

def mapping(x):
    (P,ji,bot) = dual_weak_order(len(x))
    v = bot
    for w in upper_labels(P,ji,Permutation(x)):
        v = P.join(v,w)
    return v
Properties
bijective, graded
Created
Mar 02, 2024 at 15:19 by Sam Hopkins
Updated
Mar 02, 2024 at 20:49 by Sam Hopkins
9 Comments (hide)

Martin Rubey
2 Mar 15:52
Hi Sam! Thank you for the contribution! is this related directly to https://www.findstat.org/MapsDatabase/Mp00281? Unfortunately, there is also a problem with the time the map takes to compute - the image of a random permutation on 6 elements takes 40 seconds to compute on my computer. Apparently, most of the time is spent in computing the join. I'll see whether I can make it faster.
Sam Hopkins
2 Mar 16:07
Hi Martin! I don't think it is related to that signed permutation rowmotion, although I can't say for sure because I don't understand how that signed permutation rowmotion is defined. And yes, I know my code is inefficient. To evaluate this rowmotion on a single permutation involves computing all the edge labels coming from canonical join/meet representations for the whole weak order. The problem is that the usual "fast" way of computing rowmotion, by toggling, does not work for arbitrary semidistributive lattices. In theory, understanding the specific combinatorics of canonical join representations in weak order of permutations via noncrossing arc diagrams as described by Reading in https://arxiv.org/abs/1405.6904 could lead to a faster way of computing weak order rowmotion. You might ask Nathan Williams, who I think has better code. For example, according to Section 7.11 of the Thomas--Williams paper, they computed all the rowmotion orbits up to n=7.
Martin Rubey
2 Mar 16:23
It seems to me that the biggest problem is that the code computes the full weak order. I think that this can be avoided, the join irreducibles are the elements with exactly one descent. If I cache that, computing a single image is much quicker, but still too slow. Now, most of the time is spent computing the join - even though the join matrix is available. I'll have to investigate.
Sam Hopkins
2 Mar 16:58
I think I made some adjustments to the code along the lines of what you were suggesting to speed it up a bit. Should I go ahead and edit the submission?
Martin Rubey
2 Mar 17:23
Please do! I have an intermediate version here: <pre> @cached_function def weak_order(n): fcn = lambda p, q: p.permutohedron_lequal(q) Q = LatticePoset(Poset((Permutations(n), fcn))) return Q, Q.top(), Q.join_irreducibles() def lower_labels(Q, top, J, u): mylist = [] for v in Q.lower_covers(u): my_min = top for j in J: if Q.join(j, v) == u: if Q.le(j, my_min): my_min = j mylist.append(my_min) return set(mylist) def upper_labels(Q, top, J, u): mylist = [] for v in Q.upper_covers(u): my_min = top for j in J: if Q.join(j, u) == v: if Q.le(j, my_min): my_min = j mylist.append(my_min) return set(mylist) def mapping(x): u = Permutation(x) Q, top, J = weak_order(len(x)) ll = lower_labels(Q, top, J, u) for v in Q: if upper_labels(Q, top, J, v) == ll: return v return None </pre>
Sam Hopkins
2 Mar 17:35
Okay, I went ahead and submitted the revision. It is still not super fast but maybe this is good enough?
Sam Hopkins
2 Mar 20:42
I finally found a much much faster way of writing the code! Instead of iterating through the whole symmetric group each time, we just compute the labels of the input permutation, and then take the joins of these labels. Unfortunately it means I had to write the code in a completely "dual" way compared to how it is described in the text. But it still works fine. Hopefully this is the last update.
Martin Rubey
2 Mar 23:44
Hi Sam! Thank you! I optimized a bit more, mainly by avoiding to construct the full poset. We could possibly optimize a bit more, but I think this one should work. We can now have the image of a permutation in S_14 in just below four seconds on my computer. I am guessing that it will be more interesting to find out what the map does, rather than fiddling with inversion vectors. def upper_labels(J, u): for v in u.permutohedron_pred(): cur_min = None for j in J: if ((cur_min is None or cur_min.permutohedron_lequal(j)) and v.permutohedron_lequal(j) and not u.permutohedron_lequal(j)): cur_min = j yield cur_min def mapping(x): n = len(x) bot = Permutation(range(n, 0, -1)) if n > 1: J = [x for s in Subsets(range(n-1), n-2) for x in Permutations(descents=(s, n))] else: J = [] v = bot for w in upper_labels(J, x): v = v.permutohedron_meet(w) return v
Martin Rubey
2 Mar 23:46
Oh. The map is essentially known to findstat: sage: findmap("Permutations", mapping) 0: Mp00064oMp00241 (quality [100]) sage: _[0].info() your input matches Mp00241: invert Laguerre heap: Permutations -> Permutations Mp00064: reverse: Permutations -> Permutations among the values you sent, 100 percent are actually in the database

Comment:
Name:
E-Mail:
Send e-mail on new comments:
Captcha:
Please type the top row of
captcha
add comment