- FindStat

Identifier

Mp00000: Permutations —Weak order rowmotion⟶ Permutations

Description

Any semidistributive lattice $L$ has a canonical labeling of the edges of its Hasse diagram by its join irreducible elements (see [1]). Rowmotion on this lattice is the bijection which takes an element $x \in L$ with a given set of up-labels to the unique element $y \in L$ which has that set as its down-labels (see [1] and [2]). 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 [3].

References

[1] Barnard, E. The Canonical Join Complex DOI:10.37236/7866 arXiv:1610.05137
[2] Thomas, H., Williams, N. Rowmotion in slow motion DOI:10.1112/plms.12251 arXiv:1712.10123
[3] Hopkins, S. The CDE property for skew vexillary permutations DOI:10.1016/j.jcta.2019.06.005 arXiv:1811.02404
[4] Defant, C., Williams, N. Semidistrim Lattices DOI:10.1017/fms.2023.46 arXiv:2111.08122

Sage code

def weak_order(n):
    fcn = lambda p,q : p.permutohedron_lequal(q)
    return Poset((Permutations(n), fcn))

def lower_labels(P,u):
    Q = LatticePoset(P)
    mylist = []
    for v in Q.lower_covers(u):
        my_min = Q.maximal_elements()[0]
        for j in Q.join_irreducibles():
            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(P,u):
    Q = LatticePoset(P)
    mylist = []
    for v in Q.upper_covers(u):
        my_min = Q.maximal_elements()[0]
        for j in Q.join_irreducibles():
            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):
    n = len(x)
    P = weak_order(n)
    u = Permutation(x)
    ll = lower_labels(P,u)
    for v in P:
        if upper_labels(P,v) == ll:
            return v
    return None

Properties

bijective

Created

Mar 02, 2024 at 15:19 by Sam Hopkins

Updated

Mar 02, 2024 at 15:19 by Sam Hopkins

edit this revision

Identifier

Mp00000: Permutations —Weak order rowmotion⟶ Permutations

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 up-labels to the unique element $y \in L$ which has that set as its down-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 [3].

Diff 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 up-labels to the unique element y \in L which has that set as its down-labels (see [12] and [23]). 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 [3].

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

Diff 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]]
[23] Thomas, H., Williams, N. Rowmotion in slow motion [[DOI:10.1112/plms.12251]] [[arXiv:1712.10123]]
[34] Hopkins, S. The CDE property for skew vexillary permutations [[DOI:10.1016/j.jcta.2019.06.005]] [[arXiv:1811.02404]]
[45] Defant, C., Williams, N. Semidistrim Lattices [[DOI:10.1017/fms.2023.46]] [[arXiv:2111.08122]]

Sage code

def weak_order(n):
    fcn = lambda p,q : p.permutohedron_lequal(q)
    return Poset((Permutations(n), fcn))

def lower_labels(P,ji,u):
    mylist = []
    for v in P.lower_covers(u):
        my_min = P.maximal_elements()[0]
        for j in ji:
            if P.le(j,u) and not(P.le(j,v)) and P.le(j,my_min):
                my_min = j
        mylist.append(my_min)
    return Set(mylist)

def upper_labels(P,ji,u):
    mylist = []
    for v in P.upper_covers(u):
        my_min = P.maximal_elements()[0]
        for j in ji:
            if P.le(j,v) and not(P.le(j,u)) and P.le(j,my_min):
                my_min = j
        mylist.append(my_min)
    return Set(mylist)

def mapping(x):
    n = len(x)
    P = weak_order(n)
    ji = LatticePoset(P).join_irreducibles()
    u = Permutation(x)
    ll = lower_labels(P,ji,u)
    for v in P:
        if upper_labels(P,ji,v) == ll:
            return v
    return None

Properties

bijective

Created

Mar 02, 2024 at 15:19 by Sam Hopkins

Updated

Mar 02, 2024 at 17:12 by Sam Hopkins

edit this revision

Identifier

Mp00000: Permutations —Weak order rowmotion⟶ Permutations

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

Diff 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 updown-labels to the unique element y \in L which has that set as its ~~down~~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 [3].

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

def weak_order(n):
    fcn = lambda p,q : p.permutohedron_lequal(q)
    return Poset((Permutations(n), fcn))

def lower_labels(P,ji,u):
    mylist = []
    for v in P.lower_covers(u):
        my_min = P.maximal_elements()[0]
        for j in ji:
            if P.le(j,u) and not(P.le(j,v)) and P.le(j,my_min):
                my_min = j
        mylist.append(my_min)
    return Set(mylist)

def upper_labels(P,ji,u):
    mylist = []
    for v in P.upper_covers(u):
        my_min = P.maximal_elements()[0]
        for j in ji:
            if P.le(j,v) and not(P.le(j,u)) and P.le(j,my_min):
                my_min = j
        mylist.append(my_min)
    return Set(mylist)

def mapping(x):
    n = len(x)
    P = weak_order(n)
    ji = LatticePoset(P).join_irreducibles()
    u = Permutation(x)
    ll = lower_labels(P,ji,u)
    for v in P:
        if upper_labels(P,ji,v) == ll:
            return v
    return None

Properties

bijective, graded

Created

Mar 02, 2024 at 15:19 by Sam Hopkins

Updated

Mar 02, 2024 at 17:16 by Sam Hopkins

edit this revision

Identifier

Mp00000: Permutations —Weak order rowmotion⟶ Permutations

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

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

def weak_order(n):
    fcn = lambda p,q : p.permutohedron_lequal(q)
    return Poset((Permutations(n), fcn))

def lower_labels(P,ji,top,u):
    mylist = []
    for v in P.lower_covers(u):
        my_min = top
        for j in ji:
            if P.le(j,u) and not(P.le(j,v)) and P.le(j,my_min):
                my_min = j
        mylist.append(my_min)
    return Set(mylist)

def upper_labels(P,ji,top,u):
    mylist = []
    for v in P.upper_covers(u):
        my_min = top
        for j in ji:
            if P.le(j,v) and not(P.le(j,u)) and P.le(j,my_min):
                my_min = j
        mylist.append(my_min)
    return Set(mylist)

def mapping(x):
    n = len(x)
    P = weak_order(n)
    ji = LatticePoset(P).join_irreducibles()
    top = P.maximal_elements()[0]
    u = Permutation(x)
    ll = lower_labels(P,ji,top,u)
    for v in P:
        if upper_labels(P,ji,top,v) == ll:
            return v
    return None

Properties

bijective, graded

Created

Mar 02, 2024 at 15:19 by Sam Hopkins

Updated

Mar 02, 2024 at 17:34 by Sam Hopkins

edit this revision

Identifier

Mp00000: Permutations —Weak order rowmotion⟶ Permutations

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

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

@cached_function
def weak_order(n):
    fcn = lambda p,q : p.permutohedron_lequal(q)
    P = Poset((Permutations(n), fcn))
    ji = LatticePoset(P).join_irreducibles()
    top = P.maximal_elements()[0]
    return (P,ji,top)

def lower_labels(P,ji,top,u):
    mylist = []
    for v in P.lower_covers(u):
        my_min = top
        for j in ji:
            if P.le(j,u) and not(P.le(j,v)) and P.le(j,my_min):
                my_min = j
        mylist.append(my_min)
    return Set(mylist)

def upper_labels(P,ji,top,u):
    mylist = []
    for v in P.upper_covers(u):
        my_min = top
        for j in ji:
            if P.le(j,v) and not(P.le(j,u)) and P.le(j,my_min):
                my_min = j
        mylist.append(my_min)
    return Set(mylist)

def mapping(x):
    n = len(x)
    (P,ji,top) = weak_order(n)
    u = Permutation(x)
    ll = lower_labels(P,ji,top,u)
    for v in P:
        if upper_labels(P,ji,top,v) == ll:
            return v
    return None

Properties

bijective, graded

Created

Mar 02, 2024 at 15:19 by Sam Hopkins

Updated

Mar 02, 2024 at 17:42 by Sam Hopkins

edit this revision

Identifier

Mp00000: Permutations —Weak order rowmotion⟶ Permutations

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

Diff 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 [34].

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

@cached_function
def weak_order(n):
    fcn = lambda p,q : p.permutohedron_lequal(q)
    P = Poset((Permutations(n), fcn))
    ji = LatticePoset(P).join_irreducibles()
    top = P.maximal_elements()[0]
    return (P,ji,top)

def lower_labels(P,ji,top,u):
    mylist = []
    for v in P.lower_covers(u):
        my_min = top
        for j in ji:
            if P.le(j,u) and not(P.le(j,v)) and P.le(j,my_min):
                my_min = j
        mylist.append(my_min)
    return Set(mylist)

def upper_labels(P,ji,top,u):
    mylist = []
    for v in P.upper_covers(u):
        my_min = top
        for j in ji:
            if P.le(j,v) and not(P.le(j,u)) and P.le(j,my_min):
                my_min = j
        mylist.append(my_min)
    return Set(mylist)

def mapping(x):
    n = len(x)
    (P,ji,top) = weak_order(n)
    u = Permutation(x)
    ll = lower_labels(P,ji,top,u)
    for v in P:
        if upper_labels(P,ji,top,v) == ll:
            return v
    return None

Properties

bijective, graded

Created

Mar 02, 2024 at 15:19 by Sam Hopkins

Updated

Mar 02, 2024 at 18:09 by Sam Hopkins

edit this revision

Identifier

Mp00000: Permutations —Weak order rowmotion⟶ Permutations

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

@cached_function
def weak_order(n):
    f = lambda p,q : p.permutohedron_lequal(q)
    P = Poset((Permutations(n), f))
    ji = LatticePoset(P).join_irreducibles()
    return (P,ji)

def lower_labels(P,ji,u):
    ll = []
    for v in P.lower_covers(u):
        cur_min = None
        for j in ji:
            if P.le(j,u) and not(P.le(j,v)) and (cur_min == None or P.le(j,cur_min)):
                cur_min = j
        ll.append(cur_min)
    return Set(ll)

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 Set(ul)

def mapping(x):
    n = len(x)
    (P,ji) = weak_order(n)
    u = Permutation(x)
    ll = lower_labels(P,ji,u)
    for v in P:
        if upper_labels(P,ji,v) == ll:
            return v
    return None

Properties

bijective, graded

Created

Mar 02, 2024 at 15:19 by Sam Hopkins

Updated

Mar 02, 2024 at 20:20 by Sam Hopkins

edit this revision

Identifier

Mp00000: Permutations —Weak order rowmotion⟶ Permutations

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 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 lower_labels(P,ji,u):
    ll = []
    for v in P.lower_covers(u):
        cur_min = None
        for j in ji:
            if P.le(j,u) and not(P.le(j,v)) and (cur_min == None or P.le(j,cur_min)):
                cur_min = j
        ll.append(cur_min)
    return ll

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):
    n = len(x)
    (P,ji,bot) = weak_order(n)
    u = Permutation(x)
    ll = upper_labels(P,ji,u)
    v = bot
    for w in ll:
        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:39 by Sam Hopkins

edit this revision

Identifier

Mp00000: Permutations —Weak order rowmotion⟶ Permutations

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

add comment