|
|
Structural and Algorithmic Properties of Permutation Classes
Opler, Michal ; Jelínek, Vít (advisor) ; Kozma, László (referee) ; Bouvel, Mathilde (referee)
In this thesis, we study the relationship between the structure of permutation classes and the computational complexity of different decision problems. First, we explore the structure of permutation classes through the lens of various parameters, with a particular interest in tree-width. We define novel structural properties of a general permutation class C, the most notable being the long path property. Using these properties, we infer lower bounds on the maximum tree-width attained by a permutation of length n in C. For example, we prove that any class with the long path property has unbounded tree-width. The main decision problem we consider is known as Permutation Pattern Match- ing (PPM). The input of PPM consists of a pair of permutations τ (the 'text') and π (the 'pattern'), and the goal is to decide whether τ contains π as a subpermutation. Af- ter briefly considering general PPM, we focus on its pattern-restricted variant known as C-Pattern PPM where we additionally require that the pattern π comes from a fixed class C. We derive both classical and parameterized hardness results assuming different structural properties of C. For example, we show that C-Pattern PPM is NP-complete whenever C has the long path property. Furthermore, we focus on an even more restricted variant of PPM where the text is...
|
|
|
Structural properties of hereditary permutation classes
Opler, Michal ; Jelínek, Vít (advisor) ; Valtr, Pavel (referee)
A permutation class C is splittable if it is contained in a merge of its two proper subclasses, and it is 1-amalgamable if given two permutations σ, τ ∈ C, each with a marked element, we can find a permutation π ∈ C containing both σ and τ such that the two marked elements coincide. In this thesis, we study both 1-amalgamability and splittability of permutation classes. It was previously shown that unsplittability implies 1-amalgamability. We prove that unsplittability and 1-amalgamability are not equivalent properties of permutation classes by showing that there is a permutation class that is both splittable and 1-amalgamable. Moreover, we show that there are infinitely many such classes. Our construction is based on the concept of LR-inflations or more generally on hereditary 2-colorings, which we both introduce here and which may be of independent interest. 1
|
|
|
Pattern-avoiding permutation classes
Opler, Michal ; Jelínek, Vít (advisor) ; Klazar, Martin (referee)
For a permutation π, the major index of π is the sum of all indices i such that πi > πi+1. In this thesis, we study the distribution of the major index over pattern-avoiding permutations of length n. We focus on the number Mm n (Π) of permutations of length n with major index m and avoiding the set of patterns Π. First, we are able to show that for a singleton set Π = {σ} other than some trivial cases, the values Mm n (Π) are monotonic in the sense that Mm n (Π) ≤ Mm n+1(Π). Our main result is a study of the asymptotic behaviour of Mm n (Π) as n goes to infinity. We prove that for every fixed m, Π and n large enough, Mm n (Π) is equal to a polynomial in n and moreover, we are able to determine the degrees of these polynomials for many sets of patterns. 1
|
guest ::
