The study of pattern avoidance stems from a question in computer science: which sequences of distinct numbers can be ordered by a single pass through a stack? Knuth (1968) found that these sequences are characterized by having no subsequence a, b, c, such that c < a < b. Such a subsequence has the same relative order as the permutation 231, so we say that our original sequence avoids 231.

In more general terms, pattern avoidance is a natural way to restrict the structure of permutations by forbidding subsequences with a certain relative order. This has become a popular topic in enumerative combinatorics, and it has connections to various other fields.

Determining the number of 1324-avoiding permutations of length n is the most important open problem in pattern avoidance. This thesis is comprised of two papers contributing to the inversion monotonicity conjecture by Claesson, Jelínek and Steingrímsson (2012), according to which av_n^k(1324), the number of 1324-avoiders of length n with a fixed number k of inversions, is weakly increasing in n. If the conjecture is true, it improves our understanding of the asymptotic behavior of the number of 1324-avoiders.

In Paper A, we provide an explicit formula for av_n^k(1324) for all n ≥ (k + 7)/2. The proof relies on a novel structural characterization of 1324-avoiders with few inversions. As a byproduct, we show that the inversion monotonicity conjecture holds when n ≥ (k + 7)/2.

In Paper B, we study the inversion monotonicity of classes of permutations avoiding multiple patterns. We show the sets {1324, 231} and {1324, 2314, 3214, 4213} are inversion monotone via explicit injections, and introduce a general procedure for constructing large inversion-monotone sets. We also analyze the limiting structure of large permutations with a fixed number of inversions avoiding 1324 and another pattern of length four, and prove several half-monotonicity results similar to Paper A.

Mönsterundvikning har sitt ursprung i en datavetenskaplig fråga: vilka följder av distinkta tal kan sorteras med hjälp av en enda stack? Knuth (1968) visade att dessa följder kännetecknas av att de inte innehåller någon delföljd a, b, c som uppfyller c < a < b. En sådan delföljd har samma relativa ordning som permutation 231, så vi säger att vår ursprungliga följd undviker 231.

Mer allmänt är mönsterundvikning ett naturligt sätt att begränsa strukturen av permutationer genom att förbjuda delföljder med en viss relativ ordning. Detta har blivit ett populärt ämne inom enumerativ kombinatorik, och det finns kopplingar till många andra områden.

Att bestämma antalet 1324-undvikande permutationer av längd n är det viktigaste öppna problemet inom mönsterundvikning. Denna avhandling består av två artiklar som bidrar till inv-monotonicitetsförmodan av Claesson, Jelínek och Steingrímsson (2012), som säger att av_n^k(1324), antalet 1324-undvikare av längd n med ett fixerat antal k inversioner, är svagt växande i n. Om förmodan är sann, förbättrar den vår förståelse av det asymptotiska beteendet av antalet 1324-undvikare.

I Artikel A ger vi en explicit formel för av_n^k(1324) för alla n ≥ (k + 7)/2. Beviset bygger på en ny strukturell karaktärisering av 1324-undvikare med få inversioner. En konsekvens av resultatet är att inv-monotonicitetsförmodan håller när n ≥ (k + 7)/2.

I Artikel B studerar vi inv-monotoniciteten av klasser av permutationer som undviker flera mönster. Vi visar att mängderna {1324, 231} och {1324, 2314, 3214, 4213} är inv-monotona via explicita injektioner, och introducerar en metod för att konstruera stora inv-monotona mängder. Vi analyserar också strukturen av stora permutationer med ett fixerat antal inversioner som undviker 1324 och ett annat mönster av längd fyra, och bevisar flera halvmonotonicitetsresultat liknande Artikel A.