Equivalence relations on permutations and pattern avoidance - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T11:14:31Z http://mathoverflow.net/feeds/question/13871 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/13871/equivalence-relations-on-permutations-and-pattern-avoidance Equivalence relations on permutations and pattern avoidance Henning Arnór Úlfarsson 2010-02-02T21:24:19Z 2010-05-05T13:35:59Z <p>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:</p> <blockquote> <p>What interesting equivalence relations on permutations are there?</p> </blockquote> <h2>Background/Motivation</h2> <p>By a <em>permutation of $n$</em> 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$.</p> <p>A <em>pattern</em> will also be a permutation, but we are interested in how patterns <em>occur</em> 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 <em>avoids</em> that pattern.</p> <p>Now, fix an equivalence relation on $S_n$. For any pattern $p$ we define two subsets of $S_n$:</p> <p>$X_n(p) = \lbrace \sigma \in S_n \phantom{i}|\phantom{i} \sigma \text{ and every equivalent permutation avoids } p \rbrace$</p> <p>$Y_n(p) = \lbrace \sigma \in S_n \phantom{i}|\phantom{i} \sigma \text{ avoids } p \text{ and every equivalent pattern}\rbrace$</p> <p>What I am mostly interested in is how these two sets are related.</p> <p>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 <em>bivincular</em> patterns, whose definition I'll omit here) [Note considering permutations up to cyclic shifts is equivalent to looking at circular permutations.]</p> <p>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)$.</p> <p>When the two sets <em>are</em> 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.</p> <p>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.</p> http://mathoverflow.net/questions/13871/equivalence-relations-on-permutations-and-pattern-avoidance/13946#13946 Answer by Anthony Labarre for Equivalence relations on permutations and pattern avoidance Anthony Labarre 2010-02-03T09:18:12Z 2010-02-03T09:18:12Z <p>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 <a href="http://linkinghub.elsevier.com/retrieve/pii/S0012365X01001509" rel="nofollow">Eriksson et al</a> and which can be defined as follows.</p> <p>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$. </p> <p>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:</p> <p>$$m+\pi^\circ=\overline{0}^m\ \overline{\pi_1}^m\ \overline{\pi_2}^m\ \cdots\ \overline{\pi_n}^m.$$</p> <p>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$.</p> <p>Example: let $\pi=\langle 3\ 1\ 5\ 2\ 4\ 6\rangle$; then $\pi^{\circ}=0\ 3\ 1\ 5\ 2\ 4\ 6$, and</p> <p>$$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$$</p> <p>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. </p> <p>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.</p> http://mathoverflow.net/questions/13871/equivalence-relations-on-permutations-and-pattern-avoidance/14116#14116 Answer by Gjergji Zaimi for Equivalence relations on permutations and pattern avoidance Gjergji Zaimi 2010-02-04T05:18:14Z 2010-02-04T05:18:14Z <p>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 <a href="http://mathworld.wolfram.com/WilfClass.html" rel="nofollow">Wilf Class</a>)</p> http://mathoverflow.net/questions/13871/equivalence-relations-on-permutations-and-pattern-avoidance/23584#23584 Answer by James Propp for Equivalence relations on permutations and pattern avoidance James Propp 2010-05-05T13:35:59Z 2010-05-05T13:35:59Z <p>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 <a href="http://julianwest.ca/swopp.htm" rel="nofollow">http://julianwest.ca/swopp.htm</a> looks interesting I can tell you more. </p>