The Open UniversitySkip to content
 

Packing and Counting Permutations

Sliačan, Jakub (2018). Packing and Counting Permutations. PhD thesis The Open University.

Full text available as:
[img]
Preview
PDF (Version of Record) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (1MB) | Preview
Google Scholar: Look up in Google Scholar

Abstract

A permutation class is a set of permutations closed under taking subpermutations. We study two aspects of permutation classes: enumeration and packing.

Our work on enumeration consists of two campaigns. First, we enumerate all juxtaposition classes of the form “Av(abc) next to Av(xy)”, where abc and xy are permutations of lengths three and two, respectively. We represent elements from such a juxtaposition class by Dyck paths decorated with sequences of points. Context-free grammars are then used to enumerate these decorated Dyck paths. Second, we classify as algebraic the generating functions of 1×m permutation grid classes where one cell is context-free and the remaining cells are monotone. We rely on properties of combinatorial specifications of context-free classes and use operators to express juxtapositions. Repeated application of operators resolves cases for m > 2. We provide examples to re-prove known results and give new ones. Our methods are algorithmic and could be implemented on a PC.

Our work on packing consolidates current knowledge about packing densities of 4-point permutations. We also improve the lower bounds for the packing densities of 1324 and 1342 and provide rigorous upper bounds for the packing densities of 1324, 1342, and 2413. All our bounds are within 10-4 of the true packing densities. Together with the known bounds, we have a fairly complete picture of 4-point packing densities. Additionally, we obtain several bounds (lower and upper) for permutations of length at least five. Our main tool for the upper bounds is the framework of flag algebras introduced by Razborov in 2007. We also present Permpack — a flag algebra package for permutations.

Item Type: Thesis (PhD)
Copyright Holders: 2018 The Author
Academic Unit/School: Faculty of Science, Technology, Engineering and Mathematics (STEM)
Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Item ID: 55735
Depositing User: Jakub Sliacan
Date Deposited: 19 Jul 2018 15:30
Last Modified: 08 Dec 2018 04:10
URI: http://oro.open.ac.uk/id/eprint/55735
Share this page:

Download history for this item

These details should be considered as only a guide to the number of downloads performed manually. Algorithmic methods have been applied in an attempt to remove automated downloads from the displayed statistics but no guarantee can be made as to the accuracy of the figures.

Actions (login may be required)

Policies | Disclaimer

© The Open University   contact the OU