---
abstract: |
    The cyclic shift graph of a monoid is the graph whose vertices are the elements of the monoid and whose edges connect elements that are cyclic shift related. The Patience Sorting algorithm admits two generalizations to words, from which two kinds of monoids arise, the ${{\smash{\mathrm{rps}}}}$ monoid and the ${{\smash{\mathrm{lps}}}}$ (also known as Bell) monoid. Like other monoids arising from combinatorial objects such as the plactic and the sylvester, the connected components of the cyclic shift graph of the ${{\smash{\mathrm{rps}}}}$ monoid consists of elements that have the same number of each of its composing symbols. In this paper, with the aid of the computational tool SageMath, we study the diameter of the connected components from the cyclic shift graph of the ${{\smash{\mathrm{rps}}}}$ monoid.

    Within the theory of monoids, the cyclic shift relation, among other relations, generalizes the relation of conjugacy for groups. We examine several of these relations for both the ${{\smash{\mathrm{rps}}}}$ and the ${{\smash{\mathrm{lps}}}}$ monoids.
address:
- 'Centro de Matemática e Aplicações, Faculdade de Ciências e Tecnologia, Universidade Nova de Lisboa, 2829-516 Caparica, Portugal'
- 'Centro de Matemática e Aplicações and Departamento de Matemática, Faculdade de Ciências e Tecnologia, Universidade Nova de Lisboa, 2829-516 Caparica, Portugal'
- 'Departamento de Matemática and CEMAT-CIÊNCIAS, Faculdade de Ciências, Universidade de Lisboa, Lisboa 1749-016, Portugal.'
author:
- 'Alan J. Cain'
- António Malheiro
- 'Fábio M. Silva'
bibliography:
- '\\jobname.bib'
title: Conjugacy in Patience Sorting monoids
---

Introduction {#sec:introduction}
============

Patience Sorting has its origins in the works of Mallows [@Mallows62; @10.2307/2028347] and can be regarded as an insertion algorithm on standard words over a totally ordered alphabet ${\mathcal{A}}_n=\{1<2<\dots<n\}$, that is, words over ${\mathcal{A}}_n$ containing exactly one occurrence of each of the symbols from ${\mathcal{A}}_n$. As noticed by Burstein and Lankham [@BL2005], this algorithm can be viewed as a non-recursive version of Schensted’s insertion algorithm. This perspective suggests that a construction similar to the plactic monoid must also hold for this case. The plactic monoid can be constructed as the quotient of the free monoid over ${\mathcal{A}}$ (the infinite totally ordered alphabet of natural numbers), ${\mathcal{A}}^*$, by the congruence which relates words of ${\mathcal{A}}^*$ inserting to the same (semistandard) Young tableaux under Schensted’s insertion algorithm.

According to Aldous and Diaconis [@MR1694204] we can consider two generalizations of Patience Sorting to words, which we will call the right Patience Sorting insertion and the left Patience Sorting insertion ( and  insertion, respectively, for short). Considering the alphabet ${\mathcal{A}}$, these generalizations lead to two distinct monoids, the  monoid, denoted by ${{\smash{\mathrm{rps}}}}$, and the  monoid (also known in the literature as the Bell monoid [@Maxime07]), denoted by ${{\smash{\mathrm{lps}}}}$, which are, respectively, the monoids given by the quotient of ${\mathcal{A}}^*$ by the congruence which relates words having the same insertion under the  and insertion.

In a monoid $M$, two elements $u$ and $v$, are said to be related by a cyclic shift, denoted $u{\sim_{{\mathrm{p}}}}v$, if there exists $x,y\in M$ such that $u=xy$ and $v=yx$. In their seminal work concerning the plactic monoid [@MR646486], Lascoux and Schützenberger proved that any two elements in the plactic monoid, ${{\smash{\mathrm{plac}}}}$, having the same evaluation (that is, elements that contain the same number of each generating symbol) can be obtained one from the other by applying a finite sequence of cyclic shift relations. The same characterization is known to hold for other plactic-like monoids, such as the hypoplactic monoid [@1709.03974], the Chinese monoid [@MR1847182], the sylvester monoid [@MR2081336; @MR2142078], and the taiga monoid [@1709.03974]. In Section \[subsection:conjugacy\] we show that an analogous result holds for the  monoids (of finite rank) and for the  monoid of rank $1$, ${{\smash{\mathrm{lps}}}}_1$. Note that all these monoids are multihomogeneous, that is, they are defined by presentations where the two side of each defining relation contains the same number of each generator. Thus, the evaluation of an element of the monoid corresponds to the evaluation of some (and hence any) word that represents it.

The previous results can be rewritten in another form by considering what we will call as cyclic shift graph of a monoid $M$, denoted ${{\smash{\mathrm{K}}}}(M)$, which is the undirected graph whose vertices are the elements of $M$ and whose edges connect elements that differ by a cyclic shift. So, if $M={{\smash{\mathrm{plac}}}}$ or $M={{\smash{\mathrm{rps}}}}$, or their finite analogues, then the results mentioned in the previous paragraph can be restated as saying that the connected components of ${{\smash{\mathrm{K}}}}(M)$ consist of the elements of $M$ which have the same evaluation. Thus, it follows that the connected components of ${{\smash{\mathrm{K}}}}(M)$ are finite. With the aid of the computational tool SageMath we studied the diameter of the connected components of the cyclic shift graph ${{\smash{\mathrm{K}}}}({{\smash{\mathrm{rps}}}})$. In SageMath we wrote a program based on the  insertion algorithm, which given a word of ${\mathcal{A}}^*$, outputs the connected component of ${{\smash{\mathrm{K}}}}({{\smash{\mathrm{rps}}}})$ containing the element of ${{\smash{\mathrm{rps}}}}$ that corresponds to the evaluation of the inserted word .

Aiming to parallel the result obtained by Choffrut and Merca[ş]{} [@Choffrut2013], and refined by Cain and Malheiro [@1709.03974], concerning the maximal diameter of connected components of the cyclic shift graph of the plactic monoid of finite rank, we used the tools available in the SageMath library to construct tables containing the number of vertices and the diameter of connected components from ${{\smash{\mathrm{K}}}}({{\smash{\mathrm{rps}}}}_n)$. The experimental results obtained from these calculations lead us to establish some conjectures regarding diameters of specific connected components. In Section \[subsection:cyclic\_shift\], we show that some of these conjectures are in fact true. In particular we prove that the maximum diameter of a connected components of ${{\smash{\mathrm{K}}}}({{\smash{\mathrm{rps}}}}_n)$, for $n\geq 3$, lies between $n-1$ and $2n-4$. We also draw some conclusions for the diameter of ${{\smash{\mathrm{K}}}}({{\smash{\mathrm{rps}}}}_n)$ for particular elements of ${{\smash{\mathrm{rps}}}}_n$.

The cyclic shift relation previously defined generalizes the usual conjugacy relation for groups. That is, when considering groups, the cyclic shift relation is just the usual conjugacy relation. Since for monoids this relation is, in general, not transitive, it is natural to consider the transitive closure of ${\sim_{{\mathrm{p}}}}$, which we will henceforth denote by ${{\sim}_{{\mathrm{p}}}^*}$. (Note that ${{\sim}_{{\mathrm{p}}}^*}$-classes correspond to connected components of the cyclic shift graph.) We consider two other notions of conjugacy (see [@Araujo201493; @araujo2015four] for other conjugacy notions, their properties, and relations among them). The relation ${\sim_{{\mathrm{l}}}}$ on $M$, proposed by Lallement in [@MR530552], which can be defined as follows: given $u,v\in M$ $$u{\sim_{{\mathrm{l}}}}v\ \Leftrightarrow\ \exists g\in M\ ug=gv.$$ (There is a dual notion ${\sim_{{\mathrm{r}}}}$ relating elements for which $gu=vg$, instead.) As this relation is reflexive and transitive but, in general, not symmetric, in [@MR742135], Otto considered the equivalence relation ${\sim_{{\mathrm{o}}}}$ given by the intersection of ${\sim_{{\mathrm{l}}}}$ and ${\sim_{{\mathrm{r}}}}$.

All the mentioned relations are equal in the group case, and in any monoid, ${\sim_{{\mathrm{p}}}}\ \subseteq\ {{\sim}_{{\mathrm{p}}}^*}\ \subseteq\ {\sim_{{\mathrm{o}}}}\
\subseteq\ {\sim_{{\mathrm{l}}}}$ (cf. [@Araujo201493]). Denoting by ${\sim_{{\mathrm{ev}}}}$ the binary relation that pairs elements with the same evaluation, it is easy to see that for multihomogeneous monoids ${\sim_{{\mathrm{l}}}}\
\subseteq\ {\sim_{{\mathrm{ev}}}}$ (cf. [@cm_conjugacy Lemma 3.2]), and thus for all the above multihomogeneous monoids (plactic, hypoplactic, chinese, sylvester, taiga and ) we have ${{{\sim}_{{\mathrm{p}}}^*}} = {{\sim_{{\mathrm{o}}}}} = {{\sim_{{\mathrm{l}}}}}  = {{\sim_{{\mathrm{ev}}}}}$. This property, is not a general property of multihomogeneous monoids, as it is known that in the stalactic monoid connected components of the cyclic shift graph are properly contained in ${\sim_{{\mathrm{ev}}}}$ [@1709.03974 Proposition 7.2]. In this paper we show that a similar situation occurs for  monoids of rank greater than 1, since we will prove that ${{\sim_{{\mathrm{l}}}}} \subsetneq {{\sim_{{\mathrm{ev}}}}}$ in these cases.

Preliminaries and notation
==========================

In this section we introduce the fundamental notions that we will use along the paper. For more details regarding these concepts check for instance [@1706.06884], [@MR1905123], and [@howie1995fundamentals].

Words and presentations {#alphabetswords}
-----------------------

In this paper, we denote by ${\mathcal{A}}$ the infinite totally ordered alphabet $\{1<2<\dots \}$, that is, the set of natural numbers with the usual order viewed as an alphabet. For any $n\in\mathbb{N}$, the resriction of ${\mathcal{A}}$ to the first $n$ natural numbers is denoted by ${\mathcal{A}}_n$.

In general, if $\Sigma$ is an alphabet, then $\Sigma^+$ denotes the *free semigroup* over $\Sigma$, that is, the set of non-empty words over $\Sigma$, and if $\varepsilon$ denotes the empty word, then the *free monoid* over $\Sigma$ is $\Sigma^*=
\Sigma^+\cup \{\varepsilon\}$.

Next, we define several concepts that are directly related with the notion of word. Let $w\in{\mathcal{A}}^*$. Then:

-   a word $u\in {\mathcal{A}}^*$, is said to be a *factor* of $w$ if there exist words $v_1,v_2\in {\mathcal{A}}^*$, such that $w=v_1uv_2$;

-   for any symbol $a$ in ${\mathcal{A}}$, the number of occurrences of $a$ in $w$, is denoted by ${\left|w\right|}_{a}$;

-   the *content of* $w$, is the set ${{\smash{\mathrm{cont}}}}(w)=\left\{{a}\in
        {\mathcal{A}}: {\left|w\right|}_{a}\geq 1\right\}$;

-   the *evaluation of* $w$, denoted by ${{{\mathrm{ev}}}\parens[]{w}}$, is the sequence of non-negative integers whose $a$-th term is ${\left|w\right|}_{a}$, for any $a\in {\mathcal{A}}$;

-   the word is said to be *standard* if each symbol from ${\mathcal{A}}_n$, for a given $n$, occurs exactly once.

A *monoid presentation* is a pair $(\Sigma,
\mathcal{R})$, where $\Sigma$ is an alphabet and $\mathcal{R}\subseteq
\Sigma^*\times \Sigma^*$. We say that a monoid $M$ is *defined by a presentation* $(\Sigma,\mathcal{R})$ if $M\simeq \Sigma^*/\mathcal{R}^\#$, where $\mathcal{R}^\#$ is the smallest congruence containing $\mathcal{R}$ (see [@howie1995fundamentals Proposition 1.5.9] for a combinatorial description of the smallest congruence containing a relation).

A presentation is *multihomogeneous* if, for every relation $(w,w') \in\mathcal{R}$, we have ${{{\mathrm{ev}}}\parens[]{w}}={{{\mathrm{ev}}}\parens[]{w'}}$, in other words, if $w$ and $w'$ contain the same number of each of its composing symbols. Then, a monoid is multihomogeneous if there exists a multihomogeneous presentation defining the monoid.

PS.  *tableaux* and insertion
-----------------------------

In this subsection we recall the basic concepts regarding patience sorting *tableaux*, and the insertion on such *tableaux*.

A *composition diagram* is a finite collection of boxes arranged in bottom-justified columns, where no order on the length of the columns is imposed. Let $\Sigma$ be a totally ordered alphabet. Then, an  (resp. ) *tableau over* $\Sigma$ is a composition diagram with entries from $\Sigma$, so that the sequence of entries of the boxes in each column is strictly (resp., weakly) decreasing from top to bottom, and the sequence of entries of the boxes in the bottom row is weakly (resp., strictly) increasing from left to right. So, if $$\label{exmp2}
\ytableausetup
{aligntableaux=center, boxsize=1.25em}
R=\begin{ytableau}
\none &\none  & 4 \\
4 & 5 & 3 \\
1 & 1 & 2
\end{ytableau}\ \text{ and }\  S=\begin{ytableau}
\none & 5 \\
4 & 4   \\
1 & 3 \\
1 & 2
\end{ytableau},$$ then $R$ is an  *tableau*, and $S$ is an  *tableau* both over ${\mathcal{A}}_n$, for $n \geq 5$. Henceforth, we shall often refer to an  tableau or to an  tableau simply as a PS.  tableau, not distinguishing the cases whenever they can be dealt in a similar way.

The left and right Patience Sorting monoids can be given as the quotient of the free monoid ${\mathcal{A}}^*$ over the congruence which relates words that yield the same PS.  tableau under a certain algorithm [@1706.06884 § 3.6]. This algorithm is presented in the following paragraph and merges in one the Algorithms 3.1 and 3.2 of [@1706.06884]. (Observe that we will use the notation ${{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}()$, ${{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}()$ instead of, respectively, $\mathfrak{R}_\ell()$, $\mathfrak{R}_r()$ used in [@1706.06884].)

\[alg:PSinsertion\]  

*Input:* A word $w$ over a totally ordered alphabet $\Sigma$.

*Output:* An  *tableau* ${{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(w)$ (resp., *tableau* ${{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(w)$).

*Method:*

1.  If $w=\varepsilon$, output an empty *tableau* $\emptyset$. Otherwise:

2.  $w=w_1\cdots w_n$, with $w_1,\ldots,w_n\in \Sigma$. Setting $$\begin{aligned}
            {{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(w_1)=\ytableausetup
            {boxsize=1.1em, aligntableaux=center}\begin{ytableau}
            w_1 \end{ytableau} ={{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(w_1),
            \end{aligned}$$ then, for each remaining symbol $w_j$ with $1<j\leq n$, denoting by $r_1\leq \dots\leq r_k$ (resp., $r_1< \dots< r_k$) the symbols in the bottom row of the *tableau* ${{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(w_1\cdots w_{j-1})$ (resp., ${{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(w_1\cdots w_{j-1})$), proceed as follows:

    -   if $r_k\leq w_j$ (resp., $r_k < w_j$), insert $w_j$ in a new column to the right of $r_k$ in ${{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(w_1\cdots w_{j-1})$ (resp., ${{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(
                    w_1\cdots w_{j-1})$);

    -   otherwise, if $m=\min\left\{i\in\{1,\ldots,
        k\}:w_j< r_i\right\}$, (resp. $m=\min\left\{i\in\{1,\ldots,
        k\}:w_j\leq r_i\right\}$) construct a new empty box on top of the column of ${{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(w_1\cdots w_{j-1})$ (resp. ${{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(w_1\cdots w_{j-1})$) containing $r_m$. Then bump all the symbols of the column containing $r_m$ to the box above and insert $w_j$ in the box which has been cleared and previously contained the symbol $r_m$.

    Output the resulting *tableau*.

Observe that the insertion of a given word $w=w_1\cdots w_n$ under Algorithm \[alg:PSinsertion\] is obtained through the insertion of each of its symbols, from left to right in the previously obtained tableaux (starting with the empty tableaux $\emptyset$). For instance, if $R$ is the tableau from Example \[exmp2\], and $u=4511432
\in{\mathcal{A}}^*_5$, then ${{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(u)=R$ (see Figure \[figure:extended\_insertion\]). The reader can check that ${{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(u)=S$.

$$\begin{aligned}
    &\emptyset \xleftarrow[4]{\ \ \ }\
    \ytableausetup
    {mathmode, boxsize=1.3em, aligntableaux=center}
    \begin{ytableau}
    4
    \end{ytableau}\
    \xleftarrow[5]{\ \ \ }\
    \begin{ytableau}
    4 & 5
    \end{ytableau}\
    \xleftarrow[1]{\ \ \ }\
    \begin{ytableau}
    4 & \none\\
    1 & 5
    \end{ytableau}\
    \xleftarrow[1]{\ \ \ }\
    \begin{ytableau}
    4 & 5\\
    1 & 1
    \end{ytableau}\\
    &\xleftarrow[4]{\ \ \ }\
    \begin{ytableau}
    4 & 5 & \none \\
    1 & 1 & 4
    \end{ytableau}\
    \xleftarrow[3]{\ \ \ }\
    \begin{ytableau}
    4 & 5 & 4 \\
    1 & 1 & 3
    \end{ytableau}
    \xleftarrow[2]{\ \ \ }\
    \begin{ytableau}
    \none & \none & 4\\
    4 & 5 & 3\\
    1 & 1 & 2
    \end{ytableau}={{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(u ).\
    \end{aligned}$$

The Patience Sorting monoids
----------------------------

For each $\mathrm{x}\in \{{{\mathrm{l}}},{{\mathrm{r}}}\}$, we define a binary relation ${\equiv_{{\smash{\mathrm{xps}}}}}$ in ${\mathcal{A}}^*$ in the following way: given $u,v\in{\mathcal{A}}^*$, $$u{\equiv_{{\smash{\mathrm{xps}}}}}v\quad \textrm{iff}\quad  {{\smash{\mathrm{P}}}_{\smash{\mathrm{xps}}}}(u)={{\smash{\mathrm{P}}}_{\smash{\mathrm{xps}}}}(v).$$ This relation is a congruence [@1706.06884 Proposition 3.21], and the quotient of ${\mathcal{A}}^*$ by ${\equiv_{{\smash{\mathrm{lps}}}}}$ is the so-called  monoid, denoted ${{\smash{\mathrm{lps}}}}$, and the quotient of ${\mathcal{A}}^*$ by ${\equiv_{{\smash{\mathrm{rps}}}}}$ is the  monoid which is denoted by ${{\smash{\mathrm{rps}}}}$. The rank-$n$ analogues of these monoids, denoted by ${{\smash{\mathrm{lps}}}}_n$ and ${{\smash{\mathrm{rps}}}}_n$, are obtained by restricting the alphabet and the relation to the set ${\mathcal{A}}_n^*$. Note that each equivalence class of these monoids is represented by a unique tableau, and hence we will identify elements of the monoid with their tableaux representation.

Words yielding the same PS.  tableau (and hence in the same ${\equiv_{{\smash{\mathrm{xps}}}}}$-class) have necessarily the same content, and even the same evaluation. Thus, we can refer to the content and evaluation of an element of the monoid, and similarly to the content and evaluation of a tableau. Also, we shall refer to an element of ${{\smash{\mathrm{xps}}}}_n$ (or to its tableau representative) as *standard* if one (and hence any) of its words in the ${\equiv_{{\smash{\mathrm{xps}}}}}$-class has one occurrence of each of the symbols from ${\mathcal{A}}_n$.

As shown in [@1706.06884 § 3.6 & § 3.7], the left and right Patience Sorting monoids are defined by the multihomogeneous presentations $({\mathcal{A}}^*,{\mathcal{R}}_{{\smash{\mathrm{lps}}}})$ and $({\mathcal{A}}^*,{\mathcal{R}}_{{\smash{\mathrm{rps}}}})$, where $$\begin{aligned}
 {\mathcal{R}}_{{\smash{\mathrm{lps}}}}&=\{\,(yux,yxu): m\in \mathbb{N},\, x,y,u_1,\ldots , u_m\in
{\mathcal{A}}, \\
 &\qquad   u=u_m\cdots u_1,\, x<y\leq
u_1< \cdots < u_m\,\}\end{aligned}$$ and $$\begin{aligned}
{\mathcal{R}}_{{\smash{\mathrm{rps}}}}&=\{\,(yux,yxu): m\in \mathbb{N},\, x,y,u_1,\ldots , u_m\in
{\mathcal{A}}, \\
&\qquad  u=u_m\cdots u_1,\, x\leq y<
u_1\leq \cdots \leq u_m\,\}.\end{aligned}$$ Hence, the left and right Patience Sorting monoids, and their finite rank analogues, are multihomogeneous monoids.

We have seen how to obtain a PS.  tableau from a word in ${\mathcal{A}}^*$. Now, we explain how to pass from PS.  tableaux to words representing such diagrams. Given $\textrm{x}\in \{{{\mathrm{l}}},{{\mathrm{r}}}\}$ and an $x$PS.  tableau $P$, the *column reading of* $P$ is the word obtained from reading the entries of the $x$PS.  tableau $P$, column by column, from the leftmost to the rightmost, starting on the top of each column and ending on its bottom. For example, the column reading of the  tableau $R$ in Example \[exmp2\] is $41\, 51\, 432$, while the column reading of the  tableau $S$ is $411\,
5432$.

Combinatorics of cyclic shifts {#Subsection4.1}
==============================

\[subsection:cyclic\_shift\]

As noted in the introduction, the *cyclic shift graph of* a monoid $M$, ${{\smash{\mathrm{K}}}}(M)$, is the undirected graph with vertex set $M$, whose edges connect vertices that differ by a single cyclic shift. Since, ${{\smash{\mathrm{rps}}}}$ is a multihomogeneous monoid, we have ${{{\sim}_{{\mathrm{p}}}^*}}\subseteq
{{\sim_{{\mathrm{ev}}}}}$, and thus each connected component of ${{\smash{\mathrm{K}}}}({{\smash{\mathrm{rps}}}})$ cannot contain elements with different evaluations and therefore they have finitely many vertices.

Our goal in this subsection is to study the diameter of the connected components from ${{\smash{\mathrm{K}}}}({{\smash{\mathrm{rps}}}}_n)$, which as we will show are bounded by a value that depends on the rank $n$. Note that in [@1709.03974 Example 3.1], the authors provide a finitely presented multihomogeneous monoid for which the connected components of the cyclic shift graph have unbounded diameter. Therefore, these are not particular cases of a more general result that holds for all multihomogeneous monoids.

The experimental results within this subsection were obtained with the aid of SageMath [@cocalc]. This computational tool allowed us to write a program for which: given an element of ${{\smash{\mathrm{rps}}}}_n$, provides the connected component from the cyclic shift graph of ${{\smash{\mathrm{rps}}}}_n$ containing that element.

The program starts by creating a vertex for each word from ${\mathcal{A}}^*_n$ that has the same evaluation as the given element from ${{\smash{\mathrm{rps}}}}_n$. Afterwards, it adds edges between the words that are cyclic shift related. Finally, by merging the vertices whose $x$PS. insertion is the same into a single vertex, it constructs the connected component of the cyclic shift graph of ${{\smash{\mathrm{rps}}}}_n$, ${{\smash{\mathrm{K}}}}({{\smash{\mathrm{rps}}}}_n)$, containing the given element from ${{\smash{\mathrm{rps}}}}_n$.

For instance in Figure \[fig:connected\_component\] we show the connected component of the cyclic shift graph of ${{\smash{\mathrm{rps}}}}_4$ containing the element ${{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(1234)$ that can be seen to have diameter $4$.

(0.5,-3.5) – (9.5,6); (1)

[1]{} & [2]{} & [3]{} & [4]{}

; (2) \[right of=1\]

[2]{} & &\
[1]{} & [3]{} & [4]{}

; (3) \[above of=2\]

[3]{} & [4]{}\
[1]{} & [2]{}

; (4) \[below of=2\]

[4]{} & &\
[1]{} & [2]{} & [3]{}

; (5) \[right of=2\]

[3]{} &\
[2]{} &\
[1]{} & [4]{}

; (6) \[above of=5\]

[4]{} &\
[2]{} &\
[1]{} & [3]{}

; (7) \[above of=6\]

& [4]{} &\
[1]{} & [2]{} & [3]{}

; (8) \[below of=5\]

& [3]{} &\
[1]{} & [2]{} & [4]{}

; (9) \[right of=5\]

[2]{} & [4]{}\
[1]{} & [3]{}

; (10) \[above of=9\]

[4]{}\
[3]{}\
[2]{}\
[1]{}

; (11) \[above of=10\]

& [4]{}\
& [3]{}\
[1]{} & [2]{}

; (12) \[below of=9\]

[4]{} & [3]{}\
[1]{} & [2]{}

; (13) \[right of=9\]

& & [4]{}\
[1]{} & [2]{} & [3]{}

; (14) \[above of=13\]

[4]{} &\
[3]{} &\
[1]{} & [2]{}

; (15) \[below of=13\]

[3]{} & &\
[1]{} & [2]{} & [4]{}

;

\(1) edge node (2) (1) edge node (3) (1) edge node (4) (2) edge node (3) (2) edge node (4) (2) edge node (5) (2) edge node (6) (2) edge node (7) (2) edge node (8) (3) edge \[bend right=37pt\] node (4) (3) edge node (6) (3) edge node (7) (5) edge node (6) (5) edge node (8) (5) edge node (9) (5) edge node (10) (5) edge node (11) (5) edge node (12) (6) edge node (7) (6) edge \[bend right=30pt\] node (8) (8) edge node (9) (8) edge node (12) (9) edge node (10) (9) edge \[bend right=27pt\] node (11) (9) edge node (12) (9) edge node (13) (9) edge node (14) (9) edge node (15) (10) edge node (11) (13) edge node (14) (13) edge node (15) (14) edge \[bend left=38pt\] node (15) ;

The results of computer experimentation on the diameter of connected compontents is shown in Tables \[tab:std\_cyclic\_shift\_graph\] and \[tab:cyclic\_shift\_graph\]. In Table \[tab:std\_cyclic\_shift\_graph\] we present the diameter and number of vertices in the connected component of the cyclic shift graph of standard elements of lengths $1$ up to $9$, whereas in Table \[tab:cyclic\_shift\_graph\] the same information is presented but for some (non-standard) words of given fixed evaluations.

  --- ------- ---- -------- --
   1     1     0    $n-1$   
   2     2     1    $n-1$   
   3     5     2    $2n-4$  
   4    15     4    $2n-4$  
   5    52     6    $2n-4$  
   6    203    8    $2n-4$  
   7    877    10   $2n-4$  
   8   4140    12   $2n-4$  
   9   21147   14   $2n-4$  
  --- ------- ---- -------- --

  : Examples of diameter and number of vertices in the connected component of the cyclic shift graph ${{\smash{\mathrm{K}}}}({{\smash{\mathrm{rps}}}})$ for given evaluations of standard elements.

\[tab:std\_cyclic\_shift\_graph\]

The results in Table \[tab:std\_cyclic\_shift\_graph\] suggest the following:

\[conj:diameter\_std\] The diameter of a connected component of ${{\smash{\mathrm{K}}}}({{\smash{\mathrm{rps}}}})$ containing a standard element of length $n\geq 3$ is $2n-4$.

Note that the connected components of ${{\smash{\mathrm{K}}}}({{\smash{\mathrm{rps}}}})$ and ${{\smash{\mathrm{K}}}}({{\smash{\mathrm{lps}}}})$ coincide when restricted to standard elements.

The data gathered in both Table \[tab:std\_cyclic\_shift\_graph\] and Table \[tab:cyclic\_shift\_graph\] leads us to propose the following:

\[conj:diameter\_nonstd\] The diameter of a connected component of ${{\smash{\mathrm{K}}}}({{\smash{\mathrm{rps}}}})$ containing an element with $n\geq 3$ symbols, with possible multiple appearences of each symbol, lies between $n-1$ and $2n-4$.

      Evaluation                   
  ------------------- ------- ---- ------------
          (5)            1     0      $n-1$
         (5,3)           4     1      $n-1$
        (4,1,4)         20     2    $n-1=2n-4$
       (3,3,1,2)        75     3    $n-1=2n-5$
       (1,2,4,2)        287    4     $n=2n-4$
      (1,3,2,1,2)       656    5     $n=2n-5$
      (2,1,1,2,3)       554    4    $n-1=2n-6$
      (1,2,1,2,2)       711    6    $n+1=2n-4$
     (1,1,1,3,1,2)     2409    7    $n+1=2n-5$
     (1,1,2,2,1,2)     2840    6     $n=2n-6$
     (1,2,1,1,2,2)     2373    8    $n+2=2n-4$
    (1,1,1,1,2,1,2)    6499    9    $n+2=2n-5$
    (1,1,1,2,1,1,2)    6078    8    $n+1=2n-6$
    (1,1,1,1,1,2,2)    6768    10   $n+3=2n-4$
   (1,1,1,1,1,2,1,1)   11695   11   $n+3=2n-5$
   (1,1,1,1,2,1,1,1)   11224   10   $n+2=2n-6$
   (1,1,1,1,1,1,2,1)   12002   12   $n+4=2n-4$

  : Examples of diameter and number of vertices in the connected component of the cyclic shift graph ${{\smash{\mathrm{K}}}}({{\smash{\mathrm{rps}}}})$ for given evaluations of non-standard elements.

\[tab:cyclic\_shift\_graph\]

One of the first results that was possible to obtain from the data was

\[prop:diameter12\] All elements of ${{\smash{\mathrm{rps}}}}$ containing two symbols, with the same evaluation, form a connected component of ${{\smash{\mathrm{K}}}}({{\smash{\mathrm{rps}}}})$. Furthermore, the component has diameter $1$.

As already noticed each connected component of ${{\smash{\mathrm{K}}}}({{\smash{\mathrm{rps}}}})$ cannot contain elements with different evaluations. Let $u$ and $v$ be two elements of ${{\smash{\mathrm{rps}}}}$ with the same evaluation such that ${\left|{{\smash{\mathrm{cont}}}}(w)\right|}= 2$. Suppose without loss of generality that ${{\smash{\mathrm{cont}}}}(w)=\{1,2\}$. Then, these elements are of the form ${{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(2^i1^j2^k)$, for some $i, k\in \mathbb{N}_0$ and $i+k,j\in\mathbb{N}$. So, $u={{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(2^i1^j2^k)$ and $v={{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(2^l1^n2^m)$ with $j=n$ and $i+k=l+m$. Therefore, $v={{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(2^l1^j2^m)$ and we consider the following cases:

If $i\geq l$, then $k+i-l=m$. Setting $x={{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(2^{i-l})$ and $y={{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(2^l1^j2^k)$, we have $$\begin{aligned}
    &u={{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(2^{i-l}2^l1^j2^k)={{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(2^{i-l})  {{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(2^l1^j2^k)=x  y\,
\text{ and}\\
    &v={{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(2^l1^j2^k2^{i-l})={{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(2^l1^j2^k)  {{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(2^{i-l})=y  x.
    \end{aligned}$$

Otherwise, if $i<l$, then $m+l-i=k$. Setting $x={{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(2^{i}1^{j}2^{m})$ and $y={{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(2^{l-i})$, we get $$\begin{aligned}
    &u={{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(2^{i}1^{j}2^{m}2^{l-i})={{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(2^{i}1^{j}2^{m})
{{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(2^{l-i})=x  y\, \text{ and}\\
    &v={{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(2^{l-i}2^{i}1^{j}2^{m})={{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(2^{l-i})
{{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(2^{i}1^{j}2^{m})=y  x.
    \end{aligned}$$ In both cases, $u{\sim_{{\mathrm{p}}}}v$. Therefore, the diameter of the connected component from ${{\smash{\mathrm{K}}}}({{\smash{\mathrm{rps}}}})$ containing such elements is 1. The result follows.

In the following lemma we provide an upper bound for the diameter of the connected components from ${{\smash{\mathrm{K}}}}({{\smash{\mathrm{rps}}}})$ of elements whose content is greater or equal to $3$, thus answering the upper bound part of Conjecture \[conj:diameter\_nonstd\].

By observing several connected components obtained with the program constructed with SageMath, we concluded that for any element $w\in {{\smash{\mathrm{rps}}}}$, with ${{\smash{\mathrm{cont}}}}(w)=\{1,\ldots,
n\}$ and $n\geq 3$, the element $${{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}\left((n-1)^{{{\left|w\right|}}_{n-1}}
(n-2)^{{{\left|w\right|}}_{n-2}}\cdots 3^{{\left|w\right|}_3}
2^{{\left|w\right|}_2}1^{{\left|w\right|}_1}\ n^{{{\left|w\right|}}_{n}}\right)$$ plays a key role in the connected component of ${{\smash{\mathrm{K}}}}({{\smash{\mathrm{rps}}}})$ which contains $w$. For instance, in Figure \[fig:connected\_component\], we see that the element $${{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(3214)={\color{Grey}\begin{ytableau}
{\color{black}3} & \none\\
{\color{black}2} & \none\\
{\color{black}1} & {\color{black}4}
\end{ytableau}}$$ is in the center of the connected component. Using this insight we were able to prove the following result:

\[prop:diameter\_upper\_bound\] All elements of ${{\smash{\mathrm{rps}}}}$ containing $n\geq 3$ symbols, with the same evaluation, form a connected component of ${{\smash{\mathrm{K}}}}({{\smash{\mathrm{rps}}}})$. Furthermore, the component has diameter at most $2n-4$.

Let $w$ be an element of ${{\smash{\mathrm{rps}}}}$ with ${\left|{{\smash{\mathrm{cont}}}}(w)\right|}=n\geq 3$. Suppose without loss of generality that ${{\smash{\mathrm{cont}}}}(w)=\{1,\ldots, n\}$. Since each connected component of ${{\smash{\mathrm{K}}}}({{\smash{\mathrm{rps}}}}_n)$ cannot contain elements with different evaluations, to prove this result, it suffices to check that from $w$, by applying at most $n-2$ cyclic shift relations we can always obtain the element $$w'={{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}\left((n-1)^{{\left|w\right|}_{n-1}} (n-2)^{
    {\left|w\right|}_{n-2}}\cdots 2^{{\left|w\right|}_2}1^{{\left|w\right|}_1}
    n^{{\left|w\right|}_{n}}\right)$$ of ${{\smash{\mathrm{rps}}}}$.

We will construct a path in ${{\smash{\mathrm{K}}}}({{\smash{\mathrm{rps}}}}_n)$ from $w$ to $w'$ of length at most $n-2$. We aim to find a sequence $w_0,w_1,\ldots,w_{n-2}$ of elements of ${{\smash{\mathrm{rps}}}}_n$ such that $w=w_0$, $w'=w_{n-2}$, and $w_i{\sim_{{\mathrm{p}}}}w_{i+1}$, for $i=0,\ldots, n-3$. The construction is inductive. First note that all the symbols $1$ occur in the bottom of the first column of $w$. If $w$ has only one column, then $w$ has column reading $n^{{\left|w\right|}_{n}}(n-1)^{{\left|w\right|}_{n-1}}
(n-2)^{{\left|w\right|}_{n-2}}\cdots 2^{{\left|w\right|}_2}1^{{\left|w\right|}_1}$ and applying one cyclic shift we get the intended result. Suppose $w$ has at least two columns. Let $k$ (necessarily $k\geq 2$) be the bottom symbol of the second column of $w$. Observe that any symbol $j$ less than $k$ must lie in the first column of $w$. Set $w=w_0=\dots =w_{k-1}$. We calculate the element $w_k$ from $w$ in the following way. Consider the column reading $ukv$, of $w$, for $u,v\in {\mathcal{A}}_n^*$, where $u$ is the prefix just up to before the first occurrence of a symbol $k$ occurring in the second column. Fix $w_k={{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(kv) {{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(u)$. Note that $w={{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(u) {{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(kv)$ and so $w{\sim_{{\mathrm{p}}}}w_k$.

Then, the first column of $w_k$ has column reading $k^{{\left|w\right|}_k}\dots 2^{{\left|w\right|}_2}1^{{\left|w\right|}_1}$, because all symbols in $v$ are greater or equal to $k$, and symbols in $u$ that are strictly less than $k$ appear in decreasing order. For $i\in\{k, \ldots, n-2\}$, let $w_{i}={{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}\left(u\right) {{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}\left((i+1)v\right)$ where $u$ is the prefix of the column reading of $w_{i}$ up to just before the first occurrence of a symbol $i+1$ (in the second column) and let $w_{i+1}={{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}\left((i+1)v\right)  {{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}\left(u\right)$. Using this process we ensure that the first column of $w_{i+1}$ is precisely $${{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}\left((i+1)^{{\left|w\right|}_{i+1}} i^{{\left|w\right|}_i}
    \cdots 2^{{\left|w\right|}_2} 1^{{\left|w\right|}_1}\right).$$ The result follows by induction.

Regarding the lower bound of Conjecture \[conj:diameter\_nonstd\], we are only able to establish it for standard elements of ${{\smash{\mathrm{K}}}}({{\smash{\mathrm{rps}}}})$. To prove such a result, we will use the notion of cocharge sequence for standard words over ${\mathcal{A}}$ and follow an approach similar to the one used in the case of the plactic monoid in [@1709.03974]. Note that it will be sufficient to prove the result for standard words over the alphabet ${\mathcal{A}}_n$.

For any standard word $w$ over ${\mathcal{A}}_n$, the *cocharge labels* from the symbols of $w$ are calculated as follows:

-   draw a circle, place a point $*$ somewhere on its circumference, and, starting from $*$, write $w$ anticlockwise around the circle;

-   let the cocharge label of the symbol $1$ be $0$;

-   iteratively, suppose the cocharge label of the symbol $a$ from $w$ is $k$, then proceed clockwise from the symbol $a$ to the symbol $a+1$ and:

    -   if the symbol $a+1$ of $w$ is reached without passing the point $*$, then the cocharge label of $a+1$ is $k$;

    -   otherwise, if the symbol $a+1$ is reached after passing the point $*$, then the cocharge label of $a+1$ is $k+1$.

The *cocharge sequence* of a standard word $w$, ${{\smash{\mathrm{cochseq}}}}(w)$, is the sequence of the cocharge labels from the symbols of $w$, whose $a$-th term is the cocharge label from the symbol $a$ of $w$. So, it follows from the definition that if $w$ is a standard word over ${\mathcal{A}}_n$, then ${{\smash{\mathrm{cochseq}}}}(w)$ is a sequence of length $n$.

For example, the labelling of the standard word $w=4572631$ over ${\mathcal{A}}_7$, proceeds in the following way

(0,0) circle\[radius=5mm\];

(4:-4mm) arc\[radius=4mm,start angle=-170,end angle=-10\];

(-90:2mm);

(-18:13.5mm) arc\[radius=13mm,start angle=-10,end angle=-170\];

(-165:18mm) arc\[radius=18mm,start angle=-170,end angle=-10\];

i/in [0/\*,9/4,8/5,7/7,6/2,5/6,4/3,3/1]{} [ at ($ (90-\i*30:7.8mm) $) [$\ilabel$]{}; ]{}; i/in [9/2,8/2,5/2,7/3,3/0,6/1,4/1]{} [ at ($ (90-\i*30:11.2mm) $) [$\ilabel$]{}; ]{};

and thus ${{\smash{\mathrm{cochseq}}}}(w)=(0,1,1,2,2,2,3)$.

From the definition it also follows that the cocharge sequence is a weakly increasing sequence which starts at $0$ and such that each of the remaining terms is either equal to the previous term or greater by $1$.

\[standardinvariant\] For standard words $u,v$ over ${\mathcal{A}}_n$, if $u{\equiv_{{\smash{\mathrm{rps}}}}}v$, then ${{\smash{\mathrm{cochseq}}}}(u)={{\smash{\mathrm{cochseq}}}}(v)$.

It is enough to show that any two standard words over ${\mathcal{A}}_n$ such that one is obtained from the other by applying a relation from ${\mathcal{R}}_{{{\smash{\mathrm{rps}}}}_n}$ have the same cocharge sequence.

So, there is a factor $yu_i\cdots u_1x$ of one of the standard words, with $x,y,u_1,\ldots,u_i\in{\mathcal{A}}_n$ and $x<y< u_1<\cdots <u_i$, that is changed to the factor $yxu_i\cdots u_1$ of the other. Given any symbol $a\in {\mathcal{A}}_n\setminus\{1\}$, when applying such relation, the relative position between the symbols $a$ and $a-1$ is not changed. That is, if $a-1$ occurs to the right (resp. left) of $a$ in one of the standard words, then $a-1$ also occurs to the right (resp. left) of $a$ in the other. Thus, equal symbols of these standard words have the same cocharge label and therefore the cocharge sequence of these words is the same.

Given a standard element $u$ of ${{\smash{\mathrm{rps}}}}_n$ on $n$ generators, let ${{\smash{\mathrm{cochseq}}}}(u)$ be ${{\smash{\mathrm{cochseq}}}}(w)$ for any word $w\in {\mathcal{A}}^*_n$ such that ${{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(w)=u$. Using the previous lemma we conclude that ${{\smash{\mathrm{cochseq}}}}(u)$ is well-defined.

\[prop:diameter\_lower\_bound\] The diameter of a connected component of ${{\smash{\mathrm{K}}}}({{\smash{\mathrm{rps}}}}_n)$, with $n\geq 2$, containing a standard element is at least $n-1$.

The case $n=2$ follows from Lemma \[prop:diameter12\]. Suppose $n\geq 3$.

From [@1709.03974 Lemma 2.2], we deduce that any two standard elements of ${{\smash{\mathrm{rps}}}}$ that differ by a single cyclic shift, have cocharge sequences whose corresponding terms differ by at most $1$.

The standard elements $u={{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}\left(1\cdot 2\cdots
n\right)$ and $v={{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}\left(n(n-1)\cdots 1\right)$ of ${{\smash{\mathrm{rps}}}}_n$ are in the same connected component of ${{\smash{\mathrm{K}}}}({{\smash{\mathrm{rps}}}})$ by Lemma \[prop:diameter\_upper\_bound\]. Now, notice that ${{\smash{\mathrm{cochseq}}}}(u)=(0,0,\ldots,0)$ and that ${{\smash{\mathrm{cochseq}}}}(v)=(0,1,\ldots,n-1)$. Since the last term of both sequences differs by $n-1$, the standard elements $u$ and $v$ are at distance of at least $n-1$.

For instance, in Figure \[fig:connected\_component\], the distance between the elements $${{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(1234)={\color{Grey}\begin{ytableau}
    {\color{black}1} & {\color{black}2} & {\color{black}3} & {\color{black}4}
    \end{ytableau}}\ \text{ and }\ {{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(4321)={\color{Grey}\begin{ytableau}
    {\color{black}4} \\
    {\color{black}3} \\
    {\color{black}2} \\
    {\color{black}1}
    \end{ytableau}}$$ in that connected component is precisely $3$, which is in accordance with the previous result.

Since for standard words the cyclic shif graphs ${{\smash{\mathrm{K}}}}({{\smash{\mathrm{lps}}}})$ and ${{\smash{\mathrm{K}}}}({{\smash{\mathrm{rps}}}})$ coincide, the previous result also give us a lower bound for connected components of standard words of ${{\smash{\mathrm{K}}}}({{\smash{\mathrm{lps}}}})$.

Combining Lemmata \[prop:diameter12\], \[prop:diameter\_upper\_bound\] and \[prop:diameter\_lower\_bound\] we get

1.  Connected components of ${{\smash{\mathrm{K}}}}({{\smash{\mathrm{rps}}}})$ coincide with ${\sim_{{\mathrm{ev}}}}$-classes of ${{\smash{\mathrm{rps}}}}$.

2.  The maximum diameter of a connected component of ${{\smash{\mathrm{K}}}}({{\smash{\mathrm{rps}}}}_n)$ is $n-1$, for $n=1,2$, and lies between $n-1$ and $2n-4$, for $n\geq 3$.

Other observations from computer experimental results lead us to conclude that the number of vertices in a given connected component is equal to the number of vertices in the connected component that has one more symbol $1$. This makes sense since the elements of the new connected component will be the elements of the former with an additional symbol 1 in the bottom of the first column.

Also, it seems that in a standard component, the addition of a new symbol $1$ leads to a connected component whose diameter can possibly decrease by 2 when compared with the original. In fact, we were able to establish the following result:

Let $w$ be an element of ${{\smash{\mathrm{rps}}}}$, with $n\geq 4$ symbols, such that the minimum symbol of $w$ has at least two occurences, and the second smallest symbol only occurs once. Then the diameter of the connected component of ${{\smash{\mathrm{K}}}}({{\smash{\mathrm{rps}}}})$ containing $w$ is at most $2n-6$.

Without lost of generality, suppose that ${{\smash{\mathrm{cont}}}}(w)=\{1,\dots ,n\}$, with $n\geq 4$. The proof strategy is similar to the proof of Lemma \[prop:diameter\_upper\_bound\]. We aim to construct a path in ${{\smash{\mathrm{K}}}}({{\smash{\mathrm{rps}}}})$ from $w$ to $$w'={{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}\left(1^{{\left|w\right|}_1}
    (n-1)^{{\left|w\right|}_{n-1}}(n-2)^{{\left|w\right|}_{n-2}}\cdots 3^{{\left|w\right|}_3}2
n^{{\left|w\right|}_n}\right)$$ by applying at most $n-3$ cyclic shifts relations.

For an element $w$ of ${{\smash{\mathrm{rps}}}}$, under the given assumptions, we will distinguish particular readings of its tableau representation. For simplicity, we call these readings *delayed column readings*. Note that the symbol $1$ occurs more than once, and that all symbols $1$ appear on the bottom of the first column of such tableaux. If we proceed as in the column reading, but we read the symbol on the bottom of the first column (necessarily a symbol $1$) latter on, we obtain a delayed column reading. Following Algorithm \[alg:PSinsertion\], it is clear that all these words corresponding to delayed column readings also insert to the same element. For example, the element $S$ of has column reading $411\, 5432$ and has delayed column readings, $4151432$, $4154132$, $4154312$, and $4154321$.

If the tableau representation of $w$ has only one column, then it has the form $${{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}\left(
    n^{{\left|w\right|}_n}(n-1)^{{\left|w\right|}_{n-1}}(n-2)^{{\left|w\right|}_{n-2}}\cdots
3^{{\left|w\right|}_3}2
1^{{\left|w\right|}_1}\right)$$ which is cyclic shift related to $${{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}\left(
    (n-1)^{{\left|w\right|}_{n-1}}(n-2)^{{\left|w\right|}_{n-2}}\cdots
3^{{\left|w\right|}_3}2
1^{{\left|w\right|}_1}n^{{\left|w\right|}_n}\right)$$ which in turn has delayed column reading $$(n-1)^{{\left|w\right|}_{n-1}}(n-2)^{{\left|w\right|}_{n-2}}\cdots
3^{{\left|w\right|}_3}2
1^{{\left|w\right|}_1-1}n^{{\left|w\right|}_n}1.$$ By applying a cyclic shift we get the intended form since $$w'= {{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}\left(
1(n-1)^{{\left|w\right|}_{n-1}}(n-2)^{{\left|w\right|}_{n-2}}\cdots
3^{{\left|w\right|}_3}2
1^{{\left|w\right|}_1-1}n^{{\left|w\right|}_n}\right).$$

Otherwise, suppose first that the bottom symbol of the second column is $2$. Note that the symbol $3$ can appear in the first three columns of $w$, and if it appears in the third column, then its bottom symbol is a $3$. Consider the delayed column reading of $w$, $u13v$, where $u$ is the prefix up to before the first occurence of a symbol $3$ in the rightmost column where a symbol $3$ appears (necessarily on the first three columns). So, either $u$ or $v$ has the unique symbol $2$, and if $u$ or $v$ has the symbol $2$ then all symbols $3$ appear to its left. Let $w_3={{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(13v) {{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(u)$, and so $w{\sim_{{\mathrm{p}}}}w_3$, since $w={{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(u) {{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(13v)$. The first column of $w_3$ has column reading $1^{{\left|w\right|}_1}$ and the second column $3^{{\left|w\right|}_3}2$.

Now suppose the bottom symbol of the second column is $k>2$. Consider the delayed column reading of $w$, $u1kv$, where $u$ is the prefix up to before the first occurence of a symbol $k$ in the second column. Note that all symbols in $v$ are greater or equal to $k$, and symbols in $u$ that are strictly less than $k$ appear in decreasing order (from left to right). Let $w_k={{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(1kv) {{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}(u)$, and so $w{\sim_{{\mathrm{p}}}}w_k$. The first column of $w_k$ has column reading $1^{{\left|w\right|}_1}$ and the second column $k^{{\left|w\right|}_{k}}\cdots
3^{{\left|w\right|}_3}2 $.

We will construct a path in ${{\smash{\mathrm{K}}}}({{\smash{\mathrm{rps}}}}_n)$ from $w_k$ to $w'$ of length at most $n-4$, by considering a sequence $w_k,\ldots,w_{n-1}$ of elements of ${{\smash{\mathrm{rps}}}}_n$, with $k\geq 3$, such that $w'=w_{n-1}$, and $w_i{\sim_{{\mathrm{p}}}}w_{i+1}$, for $i=k,\ldots, n-1$. For $i\in\{k, \ldots, n-2\}$, let $w_{i}={{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}\left(u\right) {{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}\left(1(i+1)v\right)$ where $u$ is the prefix of the delayed column reading $u1(i+1)v $ of $w_{i}$ up to just before the first occurrence of a symbol $i+1$ (on the third column) and let $w_{i+1}={{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}\left(1(i+1)v\right)  {{\smash{\mathrm{P}}}_{\smash{\mathrm{rps}}}}\left(u\right)$. Note that all symbols in $v$ are greater or equal to $i+1$, and all symbols in $u$ that are strictly less than $i+1$ appear in decreasing order (from left to right). Thus the two first columns of $w_{i+1}$ have column readings $1^{{\left|w\right|}_1}$ and $(i+1)^{{\left|w\right|}_{i+1}} i^{{\left|w\right|}_i}\dots
3^{{\left|w\right|}_3}2$, respectively. The result follows by induction.

Conjugacy in the  and  monoids {#subsection:conjugacy}
==============================

Restating the results of Section \[subsection:cyclic\_shift\] in terms of the conjugacy relation ${\sim_{{\mathrm{p}}}}$ we have shown that in ${{\smash{\mathrm{rps}}}}_n$ we have ${{\sim_{{\mathrm{p}}}}}={{\sim_{{\mathrm{ev}}}}}$, for $n\in\{1,2\}$; and that ${{\sim_{{\mathrm{p}}}}}\subsetneq {{{\sim}_{{\mathrm{p}}}^*}}={{\sim_{{\mathrm{ev}}}}}$, for $n>2$. Thus, ${{{\sim}_{{\mathrm{p}}}^*}}={{\sim_{{\mathrm{ev}}}}}$ in the (infinite rank) right Patience Sorting monoid. In all cases, we deduce that any of the conjugacy relations ${{{\sim}_{{\mathrm{p}}}^*}}$, ${{\sim_{{\mathrm{o}}}}}$, and ${{\sim_{{\mathrm{l}}}}}$ coincides with ${{\sim_{{\mathrm{ev}}}}}$.

The  case proves to be distinct from the  case. In ${{\smash{\mathrm{lps}}}}_1$, it is immediate that ${{\sim_{{\mathrm{p}}}}}={{\sim_{{\mathrm{ev}}}}}$, but for $n\geq 2$, we will see that ${{\sim_{{\mathrm{p}}}}}\subsetneq
{{{\sim}_{{\mathrm{p}}}^*}}$ and ${{\sim_{{\mathrm{l}}}}}\subsetneq {{\sim_{{\mathrm{ev}}}}}$, in ${{\smash{\mathrm{lps}}}}_n$, and thus in ${{\smash{\mathrm{lps}}}}$. Whether the inclusion ${{{\sim}_{{\mathrm{p}}}^*}}\subseteq {{\sim_{{\mathrm{l}}}}}$ is strict or, in fact an equality, is left as an open question.

For any $n\geq 2$, in ${{\smash{\mathrm{lps}}}}_n$ we have ${{\sim_{{\mathrm{p}}}}}\subsetneq {{{\sim}_{{\mathrm{p}}}^*}}$.

From Lemma \[prop:diameter\_lower\_bound\], we deduce that ${{\sim_{{\mathrm{p}}}}}
    \subsetneq {{{\sim}_{{\mathrm{p}}}^*}}$, for ${{\smash{\mathrm{lps}}}}_n$ with $n\geq 3$.

Regarding the ${{\smash{\mathrm{lps}}}}_2$ case, consider the elements ${{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(21121)$ and ${{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(21112)$ of ${{\smash{\mathrm{lps}}}}_2$. We have that $$\begin{aligned}
    {{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(21121)&={{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(211) {{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(21){\sim_{{\mathrm{p}}}}{{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(21) {{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(211)={{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(21211)\\
    &={{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(22111)={{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(2) {{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(2111){\sim_{{\mathrm{p}}}}{{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(2111) {{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(2)\\
    &={{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(21112),
    \end{aligned}$$ and so ${{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(21121)\ {{\sim}_{{\mathrm{p}}}^*}\ {{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(21112)$ in ${{\smash{\mathrm{lps}}}}_2$. It is easy to check that ${{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(21121){\nsim_{{\mathrm{p}}}}{{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(21112)$ in ${{\smash{\mathrm{lps}}}}_2$. Indeed, notice that the unique words $u$ and $v$ of ${\mathcal{A}}^*_2$ such that ${{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(u)={{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(21121)$ and ${{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(v)={{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(21112)$ are precisely, $21121$ and $21112$, respectively. Moreover, if ${{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(21121)={{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(st)$, for words $s,t\in{\mathcal{A}}_2^*$, then ${{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(ts)\neq {{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(21112)$.

Resuming, we have a pair of elements of ${{\smash{\mathrm{lps}}}}_2$ which belong to ${{\sim}_{{\mathrm{p}}}^*}$ but not to ${\sim_{{\mathrm{p}}}}$.

In order to prove that ${{\sim_{{\mathrm{l}}}}}\subsetneq {{\sim_{{\mathrm{ev}}}}}$, in ${{\smash{\mathrm{lps}}}}_n$, we first prove two auxiliary results.

For any $k,n\in \mathbb{N}$ and $u,v\in {{\smash{\mathrm{lps}}}}_k$, if $n\geq k$, then: $$u{\sim_{{\mathrm{l}}}}v \text{ in } {{\smash{\mathrm{lps}}}}_n\ \Leftrightarrow\ u{\sim_{{\mathrm{l}}}}v \text{ in }
    {{\smash{\mathrm{lps}}}}_k.$$

Let $u,v\in {{\smash{\mathrm{lps}}}}_k$ and $n\geq k$. Suppose that $u{\sim_{{\mathrm{l}}}}v$ in ${{\smash{\mathrm{lps}}}}_n$. Note that $u$ and $v$ have the same evaluation. There exists $g\in {{\smash{\mathrm{lps}}}}_n$ such that $u g= g v$. If $g$ is the identity then the result holds trivially. Assume that the tableau representation of $g$ has $j$ columns.

Since $u g= g v$, then $u^2g=u u g
= u g v= g v v=g v^2$. Using the same reasoning, it follows that for any $i\geq 1$, $u^i g=g v^i$. Note that if $a$ is the minimum symbol occuring in $u$, then $u^i$ has bottom row beginning (from left to right) with (at least) $i$ symbols $a$.

Suppose $g$ has a symbol greater than $k$. As ${{\smash{\mathrm{cont}}}}(u)\subseteq {\mathcal{A}}_k$, the symbols from ${g}$ that are greater or equal than $k$ have to be inserted in the tableau representation of $u^j$ to the right of the first $j$ columns. Now, in the tableau representation of $gv^i$, the symbols from $g$ are inserted into the first $j$ columns. This is a contradiction, since $u^ig=gv^i$. So all symbols from $g$ are less or equal than $k$, that is, $g\in{{\smash{\mathrm{lps}}}}_k$.

The converse direction of the lemma is obvious from the definition of ${\sim_{{\mathrm{l}}}}$.

Let $C_2=\left\{{{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(1),{{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(21)\right\}$. As proved in [@1706.06884 Proposition 4.1], the submonoid of ${{\smash{\mathrm{lps}}}}_2$ generated by $C_2$, denoted $\langle C_2\rangle$, is free. Observe that the elements of $\langle C_2\rangle$ are precisely the elements of ${{\smash{\mathrm{lps}}}}_2$ whose tableau representation has bottom row filled with symbols $1$.

\[lem:left\_conjugacy\_Bell2\] For any $u,v\in \langle C_2\rangle$ and $n\geq 2$, $$u{\sim_{{\mathrm{l}}}}v \text{ in } {{\smash{\mathrm{lps}}}}_n\ \Leftrightarrow\ u{\sim_{{\mathrm{l}}}}v
    \text{ in } \langle C_2\rangle.$$

Let $u,v\in \langle C_2\rangle$, $n\geq 2$ and suppose that $u{\sim_{{\mathrm{l}}}}v$ in ${{\smash{\mathrm{lps}}}}_n$. Suppose that $u\in\langle {{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(21)\rangle$. Since $u{\sim_{{\mathrm{ev}}}}v$, then also $v\in
\langle{{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(21)\rangle$, and thus $u=v$. Therefore the result holds.

Suppose now that $u\notin \langle {{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(21)\rangle$. Then at least one of the columns of the tableau representation of $u$ has height one and is filled with the symbol $1$. Note that the tableau representation of $v$ has the same number of columns of heigth two, and the same number of columns of heigth one (and each such box is filled with the symbol $1$).

Let $g\in {{\smash{\mathrm{lps}}}}_n$ be such that $u g= g v$. By the previous lemma we can assume $g\in{{\smash{\mathrm{lps}}}}_2$. If $g$ is the identity then the result holds trivially. Suppose that the tableau representation of $g$ has at least one column with height one filled with the symbol $2$. Attending to Algorithm \[alg:PSinsertion\] and since the bottom row of $u$ is filled with the symbol $1$, $ug$ is represented by a tableau that is composed by the columns of $u$ followed by the columns of $g$.

Now, the tableau representation of $gv$ has at least one less column. Indeed, consider the column reading of the tableau representation of $v$, which is a word from $\{1,21\}^*$, where at least one single symbol $1$ is used, that is, it does not belong to $\{21\}^*$. Applying Algorithm \[alg:PSinsertion\] we will first insert symbols from $g$, and get the tableau representation of $g$, followed by the insertion of the column reading from $v$. Now, each time a word $21$ is inserted we obtain a new column, but the first time a single symbol $1$ is inserted it will take place in the leftmost column of height one filled with the symbol $2$, becoming a column of heigth two and column reading $21$. Thus, the tableau representation of $gv$ cannot have the same number of columns as the tableau representation of $ug$. This is a contradiction. Therefore, the tableau representation of $g$ has bottom row filled with the symbol $1$, and hence $g\in\langle C_2\rangle$.

Since the converse direction is immediate, the result follows.

\[prop511\] For the  monoid of rank $n$, with $n\geq 2$, we have $${\sim_{{\mathrm{l}}}}\ \subsetneq\
{\sim_{{\mathrm{ev}}}}.$$

In the free monoid of rank $2$ the relation ${{\sim}_{{\mathrm{p}}}^*}$ is equal to ${\sim_{{\mathrm{l}}}}$ [@lentin1967combinatorial Theorem 3], and it is properly contained in ${\sim_{{\mathrm{ev}}}}$ (For example, in ${\mathcal{A}}_2^*$, there are words with the same evaluation $2121$ and $2112$, for which $2121{\nsim_{{\mathrm{l}}}}2112$).

Consider the embedding $\eta:{\mathcal{A}}_2^*\to{{\smash{\mathrm{lps}}}}_n$ given by $1\mapsto
{{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(1)$ and $2\mapsto {{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(21)$. This map yields an isomorphism between ${\mathcal{A}}_2^*$ and the free submonoid of ${{\smash{\mathrm{lps}}}}_n$, $\langle C_2\rangle$. Using the example of the first paragraph and the isomorphism, we conclude that the elements ${{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(211211)$ and ${{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(211121)$ of $\langle C_2\rangle$ that have the same evaluation, satisfy ${{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(211211) {\nsim_{{\mathrm{l}}}}{{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(211121)$ in $\langle
C_2\rangle$. By Lemma \[lem:left\_conjugacy\_Bell2\] we get ${{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(211211)
{\nsim_{{\mathrm{l}}}}{{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(211121)$ in ${{\smash{\mathrm{lps}}}}_n$. The result follows.

Regarding the relation between ${{\sim}_{{\mathrm{p}}}^*}$ and ${\sim_{{\mathrm{l}}}}$ in the  monoids of rank greater or equal than $3$ we leave the following:

In any multihomogeneous monoid the inclusion ${{\sim}_{{\mathrm{p}}}^*}\ \subseteq\ {\sim_{{\mathrm{l}}}}$ holds. For the  monoid of rank $n$, ${{\smash{\mathrm{lps}}}}_n$, with $n\geq 3$, is the inclusion strict, or does the equality hold?

Considering this problem we were able to prove the following result:

Let $u,v$ be elements of ${{\smash{\mathrm{lps}}}}_n$ with exactly two symbols (with possible multiple occurrences) and $n\geq 2$. In ${{\smash{\mathrm{lps}}}}_n$, the following holds $$u\ {{\sim}_{{\mathrm{p}}}^*}\ v\ \Leftrightarrow\ u\ {\sim_{{\mathrm{l}}}}\ v.$$

Without lost of generality, assume that $u,v\in {{\smash{\mathrm{lps}}}}_2$ and that $u{\sim_{{\mathrm{l}}}}v$ in ${{\smash{\mathrm{lps}}}}_n$. Hence $u {\sim_{{\mathrm{ev}}}}v$ and thus for $a\in{\mathcal{A}}_2$, the number of symbols $a$ in $u$ and $v$ is the same.

As $u,v\in {{\smash{\mathrm{lps}}}}_2$, $u={{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(u'u'')$ and $v={{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(v'v'')$ where ${{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(u'),{{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(v')
\in\langle C_2\rangle$, and ${{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(u''),{{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(v'')\in \langle{{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(2)\rangle$. Note that $u{\sim_{{\mathrm{p}}}}{{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(u''u')$ and $v{\sim_{{\mathrm{p}}}}{{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(v''v')$ in ${{\smash{\mathrm{lps}}}}_n$.

We consider two cases. If ${\left|u'u''\right|}_2\geq {\left|u'u''\right|}_1$, then ${{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(u''u')={{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}\left((21)^i2^j\right)$ and ${{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(v''v')
={{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}\left((21)^k2^l\right)$ for some $i,j,k,l\in\mathbb{N}_0$. As ${\left|u''u'\right|}_a={\left|v''v'\right|}_a$ for all $a\in{\mathcal{A}}_2$, we deduce that $i=k$ and $i+j=k+l$, and thus it follows that $j=l$. So, we conclude that ${{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(u''u')={{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(v''v')$. Therefore $u{\sim_{{\mathrm{p}}}}{{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(u''u')={{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(v''v'){\sim_{{\mathrm{p}}}}v$ and thus $u\ {{\sim}_{{\mathrm{p}}}^*}\ v$ in ${{\smash{\mathrm{lps}}}}_n$.

Now suppose that ${|u'u''|}_1>{|u'u''|}_2$. In this case ${{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(u''u'),
{{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(v''v')\in \langle C_2\rangle$. As in ${{\smash{\mathrm{lps}}}}_n$ ${{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(u''u') {\sim_{{\mathrm{p}}}}u$, $u{\sim_{{\mathrm{l}}}}v$, ${{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(v''v'){\sim_{{\mathrm{p}}}}v$ and ${{\sim_{{\mathrm{p}}}}}\subseteq
{{\sim_{{\mathrm{l}}}}}$, it follows that ${{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(u''u'){\sim_{{\mathrm{l}}}}{{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(v''v')$ in ${{\smash{\mathrm{lps}}}}_n$, by the transitivity of ${\sim_{{\mathrm{l}}}}$. Hence, by Lemma \[lem:left\_conjugacy\_Bell2\], ${{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(u''u'){\sim_{{\mathrm{l}}}}{{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(v''v')$ in the free monoid $\langle C_2\rangle$. In a free monoid we have ${{{\sim}_{{\mathrm{p}}}^*}} ={{\sim_{{\mathrm{l}}}}}$ [@lentin1967combinatorial Theorem 3]. Therefore ${{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(u''u')\ {{\sim}_{{\mathrm{p}}}^*}\ {{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(v''v')$ in $\langle C_2\rangle$. So, ${{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(u''u')\ {{\sim}_{{\mathrm{p}}}^*}\ {{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(v''v')$ in ${{\smash{\mathrm{lps}}}}_n$. Combining this with fact that $u{\sim_{{\mathrm{p}}}}{{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(u''u')$ and ${{\smash{\mathrm{P}}}_{\smash{\mathrm{lps}}}}(v''v'){\sim_{{\mathrm{p}}}}v$ in ${{\smash{\mathrm{lps}}}}_n$, it follows that $u\ {{\sim}_{{\mathrm{p}}}^*}\ v$ in ${{\smash{\mathrm{lps}}}}_n$.

In both cases $u\ {{\sim}_{{\mathrm{p}}}^*}\ v$ in ${{\smash{\mathrm{lps}}}}_n$ and the result follows.
