Cette thèse s'intéresse au problème de la recherche de motif dans les permutations, qui a pour objectif de savoir si un motif apparaît dans un texte, en prenant en compte que le motif et le texte sont des permutations. C'est-à-dire s'il existe des éléments du texte tel que ces éléments sont triés de la même manière et apparaissent dans le même ordre que les éléments du motif. Ce problème est NP complet. Cette thèse expose des cas particuliers de ce problème qui sont solvable en temps polynomial.Pour cela nous étudions le problème en donnant des contraintes sur le texte et/ou le motif. En particulier, le cas où le texte et/ou le motif sont des permutations qui ne contiennent pas les motifs 2413 et 3142 (appelé permutation séparable) et le cas où le texte et/ou le motif sont des permutations qui ne contiennent pas les motifs 213 et 231 sont considérés. Des problèmes dérivés de la recherche de motif et le problème de la recherche de motif bivinculaire sont aussi étudiés. / This thesis focuses on permutation pattern matching problem, which askswhether a pattern occurs in a text where both the pattern and text are permutations.In other words, we seek to determine whether there exist elements ofthe text such that they are sorted and appear in the same order as the elementsof the pattern. The problem is NP-complete. This thesis examines particularcases of the problem that are polynomial-time solvable.For this purpose, we study the problem by giving constraints on the permutationstext and/or pattern. In particular, the cases in which the text and/orpattern are permutations in which the patterns 2413 and 3142 do not occur(also known as separable permutations) and in which the text and/or patternare permutations in which the patterns 213 and 231 do not occur (also known aswedge permutations) are also considered. Some problems related to the patternmatching and the permutation pattern matching with bivincular pattern arealso studied.

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