A permutation is an ordering of the letters 1, . . . , n. A permutation σ occurs as a pattern in a permutation π if there is a subsequence of π whose letters appear in the same relative order of size as the letters of σ, such a subsequence is called an occurrence. The set of all permutations, ordered by pattern containment, is a poset. In this thesis we study the behaviour of the Möbius function and topology of the permutation poset. The first major result in this thesis is on the Möbius function of intervals [1,π], such that π = π₁π₂. . . πn has exactly one descent, where a descent occurs at position i if πi > π i+1. We show that the Möbius function of these intervals can be computed as a function of the positions and number of adjacencies, where an adjacency is a pair of letters in consecutive positions with consecutive increasing values. We then alter the definition of adjacencies to be a maximal sequence of letters in consecutive positions with consecutive increasing values. An occurrence is normal if it includes all letters except (possibly) the first one of each of all the adjacencies. We show that the absolute value of the Möbius function of an interval [σ, π] of permutations with a fixed number of descents equals the number of normal occurrences of σ in π. Furthermore, we show that these intervals are shellable, which implies many useful topological properties. Finally, we allow adjacencies to be increasing or decreasing and apply the same definition of normal occurrence. We present a result that shows the Möbius function of any interval of permutations equals the number of normal occurrences plus an extra term. Furthermore, we conjecture that this extra term vanishes for a significant proportion of intervals.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:668893 |
| Date | January 2015 |
| Creators | Smith, Jason P. |
| Publisher | University of Strathclyde |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | http://oleg.lib.strath.ac.uk:80/R/?func=dbin-jump-full&object_id=25942 |
Page generated in 0.0036 seconds