Equivalence relations on permutations and pattern avoidance

Question

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.

Answer 1

Over the past year Steve Linton, Tom Roby, Julian West and I have looked at equivalence relations on permutations arising from "constrained swapping" or more generally "pattern replacement" (Knuth equivalence is a special case). If http://julianwest.ca/swopp.htm looks interesting I can tell you more.

Answer 2

Interesting question! The first two things that come to my mind are conjugacy classes (two permutations are equivalent if they have the same cycle structure), and so-called "toric permutations", introduced by Eriksson et al and which can be defined as follows.

Let $\pi$ be a permutation of {$1,2,\ldots,n$}. First, build a circular permutation $\pi^\circ=0\ \pi_1\ \pi_2\ \cdots\ \pi_n$, with indices taken modulo $n+1$ so that $0=\pi^\circ_0=\pi^\circ_{n+1}.$ This circular permutation can be read starting from any position, and the original ``linear'' permutation is reconstructed by taking the element following $0$ as $\pi_1$ and removing $0$.

Then, for $x$ in $\{0, 1, 2, \ldots, n\}$, let $\overline{x}^m = (x+m)\pmod{n+1}$, and define the following operation on circular permutations:

$$m+\pi^\circ=\overline{0}^m\ \overline{\pi_1}^m\ \overline{\pi_2}^m\ \cdots\ \overline{\pi_n}^m.$$

The toric permutation $\pi^\circ_\circ$ obtained from $\pi$ in $S_n$ is then defined as the set of permutations in $S_n$ reconstructed from all circular permutations $m+\pi^\circ$ with $0\leq m\leq n$, and we say that two permutations $\pi$, $\sigma$ in $S_n$ are torically equivalent if $\sigma\in\pi^\circ_\circ$ (or $\pi\in\sigma^\circ_\circ$), which we also write as $\pi\equiv^\circ_\circ\sigma$.

Example: let $\pi=\langle 3\ 1\ 5\ 2\ 4\ 6\rangle$; then $\pi^{\circ}=0\ 3\ 1\ 5\ 2\ 4\ 6$, and

$$ 0+\pi^{\circ}= 0\ 3\ 1\ 5\ 2\ 4\ 6$$ $$ 1+\pi^{\circ} = 1\ 4\ 2\ 6\ 3\ 5\ 0$$ $$ 2+\pi^{\circ} = 2\ 5\ 3\ 0\ 4\ 6\ 1$$ $$ 3+\pi^{\circ} = 3\ 6\ 4\ 1\ 5\ 0\ 2 $$ $$ 4+\pi^{\circ} = 4\ 0\ 5\ 2\ 6\ 1\ 3 $$ $$ 5+\pi^{\circ} = 5\ 1\ 6\ 3\ 0\ 2\ 4 $$ $$ 6+\pi^{\circ} = 6\ 2\ 0\ 4\ 1\ 3\ 5 $$

which yields $\pi_{\circ}^{\circ}$={$\langle 3\ 1\ 5\ 2\ 4\ 6\rangle, \langle 1\ 4\ 2\ 6\ 3\ 5\rangle, \langle 4\ 6\ 1\ 2\ 5\ 3\rangle, \langle 2\ 3\ 6\ 4\ 1\ 5\rangle, \langle 5\ 2\ 6\ 1\ 3\ 4\rangle$, $\langle 2\ 4\ 5\ 1\ 6\ 3\rangle, \langle 4\ 1\ 3\ 5\ 6\ 2\rangle$}, and all permutations in that set are torically equivalent.

No guarantee as to how interesting the relations between $X_n(\rho)$ and $Y_n(\rho)$ will be in these cases, but that's something to start with.

Answer 3

The first equivalence relation that comes to mind when talking about pattern avoidance is Wilf equivalence. (two permutations being Wilf equivalent iff they belong to the same Wilf Class)