A Formula for the Möbius Function of the Permutation Poset Based on a Topological Decomposition
The poset P of all permutations ordered by pattern containment is a fundamental object of study in the field of permutation patterns. This poset has a very rich and complex topology and an understanding of its Möbius function has proved particularly elusive, although results have been slowly emergin...
| Main Author: | |
|---|---|
| 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/6376/pdf |
| _version_ | 1797270241444626432 |
|---|---|
| author | Jason P Smith |
| author_facet | Jason P Smith |
| author_sort | Jason P Smith |
| collection | DOAJ |
| description | The poset P of all permutations ordered by pattern containment is a fundamental object of study in the field of permutation patterns. This poset has a very rich and complex topology and an understanding of its Möbius function has proved particularly elusive, although results have been slowly emerging in the last few years. Using a variety of topological techniques we present a two term formula for the Mo ̈bius function of intervals in P. The first term in this formula is, up to sign, the number of so called normal occurrences of one permutation in another. Our definition of normal occurrences is similar to those that have appeared in several variations in the literature on the Möbius function of this and other posets, but simpler than most of them. The second term in the formula is (still) complicated, but we conjecture that it equals zero for a significant proportion of intervals. We present some cases where the second term vanishes and others where it is nonzero. Computing the Möbius function recursively from its definition has exponential complexity, whereas the computation of the first term in our formula is polynomial and the exponential part is isolated to the second term, which seems to often vanish. This is thus the first polynomial time formula for the Möbius function of what appears to be a large proportion of all intervals of P. |
| first_indexed | 2024-04-25T02:01:08Z |
| format | Article |
| id | doaj.art-d916ad872ef94645ab82bb8d84657651 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:01:08Z |
| publishDate | 2020-04-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-d916ad872ef94645ab82bb8d846576512024-03-07T14:55:20ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502020-04-01DMTCS Proceedings, 28th...10.46298/dmtcs.63766376A Formula for the Möbius Function of the Permutation Poset Based on a Topological DecompositionJason P Smith0Department of Computer and Information Sciences [Univ Strathclyde]The poset P of all permutations ordered by pattern containment is a fundamental object of study in the field of permutation patterns. This poset has a very rich and complex topology and an understanding of its Möbius function has proved particularly elusive, although results have been slowly emerging in the last few years. Using a variety of topological techniques we present a two term formula for the Mo ̈bius function of intervals in P. The first term in this formula is, up to sign, the number of so called normal occurrences of one permutation in another. Our definition of normal occurrences is similar to those that have appeared in several variations in the literature on the Möbius function of this and other posets, but simpler than most of them. The second term in the formula is (still) complicated, but we conjecture that it equals zero for a significant proportion of intervals. We present some cases where the second term vanishes and others where it is nonzero. Computing the Möbius function recursively from its definition has exponential complexity, whereas the computation of the first term in our formula is polynomial and the exponential part is isolated to the second term, which seems to often vanish. This is thus the first polynomial time formula for the Möbius function of what appears to be a large proportion of all intervals of P.https://dmtcs.episciences.org/6376/pdfcombinatorics[math.math-co]mathematics [math]/combinatorics [math.co] |
| spellingShingle | Jason P Smith A Formula for the Möbius Function of the Permutation Poset Based on a Topological Decomposition Discrete Mathematics & Theoretical Computer Science combinatorics [math.math-co]mathematics [math]/combinatorics [math.co] |
| title | A Formula for the Möbius Function of the Permutation Poset Based on a Topological Decomposition |
| title_full | A Formula for the Möbius Function of the Permutation Poset Based on a Topological Decomposition |
| title_fullStr | A Formula for the Möbius Function of the Permutation Poset Based on a Topological Decomposition |
| title_full_unstemmed | A Formula for the Möbius Function of the Permutation Poset Based on a Topological Decomposition |
| title_short | A Formula for the Möbius Function of the Permutation Poset Based on a Topological Decomposition |
| title_sort | formula for the mobius function of the permutation poset based on a topological decomposition |
| topic | combinatorics [math.math-co]mathematics [math]/combinatorics [math.co] |
| url | https://dmtcs.episciences.org/6376/pdf |
| work_keys_str_mv | AT jasonpsmith aformulaforthemobiusfunctionofthepermutationposetbasedonatopologicaldecomposition AT jasonpsmith formulaforthemobiusfunctionofthepermutationposetbasedonatopologicaldecomposition |