Thesis

On the Möbius function and topology of the permutation poset

Downloadable Content

Download PDF
Creator
Rights statement
Awarding institution
  • University of Strathclyde
Date of award
  • 2015
Thesis identifier
  • T14140
Person Identifier (Local)
  • 201256929
Qualification Level
Qualification Name
Department, School or Faculty
Abstract
  • 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.
Resource Type
DOI
EThOS ID
  • uk.bl.ethos.668893
Date Created
  • 2015
Former identifier
  • 1237934

Relations

Items

Thumbnail Title Date Uploaded Visibility Actions
file details PDF of thesis T14140 2021-07-02 Public Download