On intervals of the consecutive pattern poset
The consecutive pattern poset is the infinite partially ordered set of all permutations where σ ≤ τ if τ has a subsequence of adjacent entries in the same relative order as the entries of σ. We study the structure of the intervals in this poset from topological, poset-theoretic, and enumerative pers...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2020-04-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/6380/pdf |
| _version_ | 1827323949053116416 |
|---|---|
| author | Sergi Elizalde Peter R. W. McNamara |
| author_facet | Sergi Elizalde Peter R. W. McNamara |
| author_sort | Sergi Elizalde |
| collection | DOAJ |
| description | The consecutive pattern poset is the infinite partially ordered set of all permutations where σ ≤ τ if τ has a subsequence of adjacent entries in the same relative order as the entries of σ. 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 Mo ̈bius function equal to zero. |
| first_indexed | 2024-04-25T02:00:51Z |
| format | Article |
| id | doaj.art-a0cc1ee5cc004956bf44743cc06b85d2 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:00:51Z |
| publishDate | 2020-04-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-a0cc1ee5cc004956bf44743cc06b85d22024-03-07T14:55:20ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502020-04-01DMTCS Proceedings, 28th...10.46298/dmtcs.63806380On intervals of the consecutive pattern posetSergi Elizalde0Peter R. W. McNamaraDepartment of Mathematics [Dartmouth]The consecutive pattern poset is the infinite partially ordered set of all permutations where σ ≤ τ if τ has a subsequence of adjacent entries in the same relative order as the entries of σ. 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 Mo ̈bius function equal to zero.https://dmtcs.episciences.org/6380/pdf[math.math-co]mathematics [math]/combinatorics [math.co] |
| spellingShingle | Sergi Elizalde Peter R. W. McNamara On intervals of the consecutive pattern poset Discrete Mathematics & Theoretical Computer Science [math.math-co]mathematics [math]/combinatorics [math.co] |
| title | On intervals of the consecutive pattern poset |
| title_full | On intervals of the consecutive pattern poset |
| title_fullStr | On intervals of the consecutive pattern poset |
| title_full_unstemmed | On intervals of the consecutive pattern poset |
| title_short | On intervals of the consecutive pattern poset |
| title_sort | on intervals of the consecutive pattern poset |
| topic | [math.math-co]mathematics [math]/combinatorics [math.co] |
| url | https://dmtcs.episciences.org/6380/pdf |
| work_keys_str_mv | AT sergielizalde onintervalsoftheconsecutivepatternposet AT peterrwmcnamara onintervalsoftheconsecutivepatternposet |