The structure of the consecutive pattern poset

Abstract

The consecutive pattern poset is the infinite partially ordered set of all permutations where $\sigma \le \tau$ if $\tau$ has a subsequence of adjacent entries in the same relative order as the entries of $\sigma$. We study the structure of the intervals in this poset from topological, poset-theoretic, and enumerative perspectives. In particular, we prove that all intervals are rank-unimodal and strongly Sperner, and we characterize disconnected and shellable intervals. We also show that most intervals are not shellable and have Möbius function equal to zero.

29 pages, 7 figures. To appear in IMRN

References in corpus (4)

• The number of permutations realized by a shift
• Clusters, generating functions and asymptotics for consecutive patterns in permutations
• On the topology of the permutation pattern poset
• The most and the least avoided consecutive patterns