Pattern avoidance in poset permutations (Q304187): Difference between revisions

A permutation on an \(n\)-element partially ordered set \((P,<)\) is a bijection \(\sigma: \, \{1,2,\ldots n\} \rightarrow P\) and \(S_{P}\) is the set of all permutations of \(P\). For another \(k\)-element poset \(Q\), \(\sigma\in S_{P}\) is said to contain \(\pi\in S_{Q}\) if it has entries \(\sigma_{i_{1}}, \sigma_{i_{2}}, \dots, \sigma_{i_{k}}\) with \(i_{1}<i_{2}<\dots < i_{k}\) and, for any \(1\leq a,b\leq k\) the order relation between \(\sigma_{i_{a}}\) and \(\sigma_{i_{b}}\) is the same as that between \(\pi_{a}\) and \(\pi_{b}\). (The order relation between two distinct elements is either `less than', `greater than' or `incomparable'). It will be seen that this generalises the definition of a pattern in a standard permutation. We let \(\text{Av}_{P}(\pi)\) be the number of permutations on \(P\) which avoid the pattern \(\pi\). In the classical situation where \(P\) is totally ordered, we omit the subscript from the notation: in this case, counting permutations which do not contain a given pattern is a long-standing active topic, see e.g. [\textit{E. Steingrimsson}, ``Some open problems on permutation patterns'', Preprint, \url{arXiv:1210.7320}] for a recent survey. In the classical situation, the number of permutations avoiding each of the six possible three letter patterns, namely 123, 132, 321, 213, 231, 312 is the same -- namely the Catalan number \(C_{n}={2n\choose n}/(n+1)\). The article under review aims to render precise the intuition that, in the poset situation, there should be at least as many structures which avoid ``small-medium-large'' substructures of length 3 than others of length 3, because ``small-medium-large'' substructures are easier to fit together. The main rigorous result is that \(\text{Av}_{P}(132)\leq \text{Av}_{P}(123)\) for any poset \(P\). Interestingly, the authors can also show that there is strict inequality if and only if \(P\) contains one of three particular 5-vertex posets \(Q_{1}\), \(Q_{2}\) and \(Q_{3}\) as an induced subposet. The proof is in some sense a development of the proof by \textit{R. Simion} and \textit{F. W. Schmidt} [Eur. J. Comb. 6, 383--406 (1985; Zbl 0615.05002)] of the fact that in the classical case \(\text{Av}(132)=\text{Av}(123)\). Various applications and open problems are also noted.