Variations of Stack Sorting and Pattern Avoidance
- Publication Type:
- Thesis
- Issue Date:
- 2020
Open Access
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is open access.
Sorting is a process of arranging certain objects into an ordered sequence. Real world problems such as sorting using switchyard networks, genome arrangement, and delivery of network data packets can be realised as sorting problems. The study of these problems can be translated into the study of sorting permutations using a system of data structures which can store and output data. For instance, the sorting problem in certain switchyard networks can be formulated as the problem of sorting permutations using 𝘴𝘵𝘢𝘤𝘬𝘴. The results of this thesis address the following research questions related to sorting permutations.
Open research questions
1. In a sorting process with a finite stack followed by an infinite stack in series, what is the depth of the finite stack at which the basis becomes infinite?
2. Is there a pattern avoidance characterisation for k-pass pop stack sortable permutations?
Apart from answering these questions, we develop a new notion of barred pattern avoidance to accommodate some of the limitations in the existing barred pattern avoidance definition. With the new notion of barred pattern avoidance, a proof can be established to answer question 2 above.
The organisation of this thesis is as follows. Chapter 1 gives a detailed introduction to the research in permutation patterns and stack sorting. It includes some history and some major research outcomes. Moreover, several variations of sorting machines are described. Finally, a few types of non-classical patterns are explained. Chapter 2 answers the first question above. Based on some experimental data, a conjecture was made that the basis changes from finite to infinite when the depth of the finite stack is 3. We found an infinite antichain in the form of extendable sequence of numbers to prove the conjecture. Chapter 3 answers the second question and introduces a new notion of barred pattern avoidance to characterise permutations sortable by a k-pass pop-stack. Then, we finish the chapter by proving the number of forbidden patterns that the permutations sortable by k-pass pop-stack must avoid is finite. The set of forbidden patterns can be algorithmically constructed. Chapter 4 concludes the thesis with some directions for future research.
Please use this identifier to cite or link to this item: