University of Strathclyde website
Digital Collections - University of Strathclyde Library
Search Results Previous Searches E-Shelf
Login End Session
Search 'System Number= 000004251' in 'General Silo' Collection [ Sorted by: Name/Title ] Refine search
Table view Full view
Record 1 of 1 1
Add to E-Shelf
e-item icon
PDF of thesis T14140 PDF of thesis T14140 - (615 K)
Title On the Möbius function and topology of the permutation poset / Jason P. Smith.
Name Smith, Jason P. .
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.
Publication date 2015
Name University of Strathclyde. Dept. of Computer and Information Sciences.
Thesis note Thesis PhD University of Strathclyde 2015 T14140
System Number 000004251

Powered by Digitool Contact us Electronic Library Services Library Home