I'm working on the interaction between equivalence relations on permutations and pattern avoidance. I've only considered Knuth equivalence and cyclic shifts until now and I'm looking for other equivalence relations to test some conjectures on. So my question is:

What interesting equivalence relations on permutations are there?

Background/Motivation

By a permutation of $n$ I mean a bijection $\lbrace 1,2,\dots,n\rbrace \to \lbrace 1,2,\dots,n \rbrace$. The set of all permutations of $n$ will be denoted $S_n$. I'll use the one-line notation for permutations, e.g., $132$ means the permutation $1\to1$, $2\to3$, $3\to2$.

A pattern will also be a permutation, but we are interested in how patterns occur in permutations. E.g., the pattern $132$ occurs in the permutation $215314$ as the letters $2$, $5$, $3$, because these have the same relative order as the pattern. Note that the letters do not have to be adjacent in the permutation. When a pattern does not occur in a permutation we say that the permutation avoids that pattern.

Now, fix an equivalence relation on $S_n$. For any pattern $p$ we define two subsets of $S_n$:

$X_n(p) = \lbrace \sigma \in S_n \phantom{i}|\phantom{i} \sigma \text{ and every equivalent permutation avoids } p \rbrace$

$Y_n(p) = \lbrace \sigma \in S_n \phantom{i}|\phantom{i} \sigma \text{ avoids } p \text{ and every equivalent pattern}\rbrace$

What I am mostly interested in is how these two sets are related.

Example: Assume our equivalence relation is cyclic shifts, meaning that two permutations (or patterns) $p$, $q$ are equivalent if we can write $p = r_1 * r_2$ and $q = r_2 * r_1$ where $*$ means concatenation. E.g., $1234$ is equivalent to $3412$. Here the two sets $X_n(p)$ and $Y_n(p)$ are equal for any $p$. (This is also true if we generalize our patterns to bivincular patterns, whose definition I'll omit here) [Note considering permutations up to cyclic shifts is equivalent to looking at circular permutations.]

Example: If our equivalence relation is Knuth equivalence, meaning that two permutations (or patterns) are equivalent if they have the same insertion tableaux under the RSK-correspondence, then the two sets are not always the same. They are the same for any pattern of length $3$, but $X_4(1324) \neq Y_4(1324)$.

When the two sets are equal then counting $Y_n(p)$ can sometimes be done more easily by looking at $X_n(p)$. When the relation is Knuth equivalence one can use the hook-length formula for instance.

So I would very happy if someone could tell me about other interesting equivalence relations on permutations so I could see how $X_n(p)$ and $Y_n(p)$ are related in other cases.

1

Equivalence relations on permutations and pattern avoidance

I'm working on the interaction between equivalence relations on permutations and pattern avoidance. I've only considered Knuth equivalence and cyclic shifts until now and I'm looking for other equivalence relations to test some conjectures on. So my question is:

What interesting equivalence relations on permutations are there?

Background/Motivation

By a permutation of $n$ I mean a bijection $\lbrace 1,2,\dots,n\rbrace \to \lbrace 1,2,\dots,n \rbrace$. The set of all permutations of $n$ will be denoted $S_n$. I'll use the one-line notation for permutations, e.g., $132$ means the permutation $1\to1$, $2\to3$, $3\to2$.

A pattern will also be a permutation, but we are interested in how patterns occur in permutations. E.g., the pattern $132$ occurs in the permutation $215314$ as the letters $2$, $5$, $3$, because these have the same relative order as the pattern. Note that the letters do not have to be adjacent in the permutation. When a pattern does not occur in a permutation we say that the permutation avoids that pattern.

Now, fix an equivalence relation on $S_n$. For any pattern $p$ we define two subsets of $S_n$:

$X_n(p) = \lbrace \sigma \in S_n \phantom{i}|\phantom{i} \sigma \text{ and every equivalent permutation avoids } p \rbrace$

$Y_n(p) = \lbrace \sigma \in S_n \phantom{i}|\phantom{i} \sigma \text{ avoids } p \text{ and every equivalent pattern}\rbrace$

What I am mostly interested in is how these two sets are related.

Example: Assume our equivalence relation is cyclic shifts, meaning that two permutations (or patterns) $p$, $q$ are equivalent if we can write $p = r_1 * r_2$ and $q = r_2 * r_1$ where $*$ means concatenation. E.g., $1234$ is equivalent to $3412$. Here the two sets $X_n(p)$ and $Y_n(p)$ are equal for any $p$. (This is also true if we generalize our patterns to bivincular patterns, whose definition I'll omit here)

Example: If our equivalence relation is Knuth equivalence, meaning that two permutations (or patterns) are equivalent if they have the same insertion tableaux under the RSK-correspondence, then the two sets are not always the same. They are the same for any pattern of length $3$, but $X_4(1324) \neq Y_4(1324)$.

When the two sets are equal then counting $Y_n(p)$ can sometimes be done more easily by looking at $X_n(p)$. When the relation is Knuth equivalence one can use the hook-length formula for instance.

So I would very happy if someone could tell me about other interesting equivalence relations on permutations so I could see how $X_n(p)$ and $Y_n(p)$ are related in other cases.