For the poset of classical permutation patterns, the first results about its Möbius function were obtained by Sagan and Vatter. Further results have been found by Steingrimsson and Tenner and by Burstein, Jelinek, Jelinkova and Steingrimsson. The general problem in this case of classical patterns seems quite hard. In contrast, the poset of consecutive pattern containment has a much simpler structure. Here we compute the Möbius function of that poset. In most cases our results give an immediate answer. In the remaining cases, we give a polynomial time recursive algorithm to compute the Möbius function. In particular, we show that the Möbius function only takes the values −1, 0 and 1.
The Moebius function of the consecutive pattern poset / A. Bernini; L. Ferrari; E. Steingrimsson. - STAMPA. - (2012), pp. 1-1. (Intervento presentato al convegno Permutation Patterns 2012 tenutosi a Glasgow, Scotland (UK) nel 11-15 giugno 2012).
The Moebius function of the consecutive pattern poset
BERNINI, ANTONIO;FERRARI, LUCA;
2012
Abstract
For the poset of classical permutation patterns, the first results about its Möbius function were obtained by Sagan and Vatter. Further results have been found by Steingrimsson and Tenner and by Burstein, Jelinek, Jelinkova and Steingrimsson. The general problem in this case of classical patterns seems quite hard. In contrast, the poset of consecutive pattern containment has a much simpler structure. Here we compute the Möbius function of that poset. In most cases our results give an immediate answer. In the remaining cases, we give a polynomial time recursive algorithm to compute the Möbius function. In particular, we show that the Möbius function only takes the values −1, 0 and 1.I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.