The Moebius function of the consecutive pattern poset

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.