kth.sePublikationer KTH
Driftinformation
Ett driftavbrott i samband med versionsuppdatering är planerat till 17/11-2026, kl 12.00-13.00. Under den tidsperioden kommer DiVA inte att vara tillgängligt.
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Inversions in the 1324-avoiding permutations
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Algebra, kombinatorik och topologi.ORCID-id: 0009-0001-7064-9492
2026 (Engelska)Licentiatavhandling, sammanläggning (Övrigt vetenskapligt)Alternativ titel
Inversioner i de 1324-undvikande permutationerna (Svenska)
Abstract [en]

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 avnk(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 avnk(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.

Abstract [sv]

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 avnk(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 avnk(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.

Ort, förlag, år, upplaga, sidor
Stockholm: KTH Royal Institute of Technology, 2026. , s. ix, 194
Serie
TRITA-SCI-FOU ; 2026:07
Nyckelord [en]
Permutation, Pattern, 1324, Inversion, Enumeration
Nyckelord [sv]
Permutation, Mönster, 1324, Inversion, Uppräkning
Nationell ämneskategori
Diskret matematik
Identifikatorer
URN: urn:nbn:se:kth:diva-378951ISBN: 978-91-8106-559-6 (tryckt)OAI: oai:DiVA.org:kth-378951DiVA, id: diva2:2050045
Presentation
2026-04-28, D3, Lindstedtsvägen 9, Stockholm, 13:00 (Engelska)
Opponent
Handledare
Forskningsfinansiär
Vetenskapsrådet, 2022-03875
Anmärkning

QC 2026-04-07

Tillgänglig från: 2026-04-07 Skapad: 2026-03-31 Senast uppdaterad: 2026-06-29Bibliografiskt granskad
Delarbeten
1. Enumerating 1324-avoiders with few inversions
Öppna denna publikation i ny flik eller fönster >>Enumerating 1324-avoiders with few inversions
2025 (Engelska)Ingår i: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 32, nr 3, artikel-id P3.44Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We enumerate the numbers avkn(1324) of 1324-avoiding n-permutations with exactly k inversions for all k and n≥(k+7)/2. The result depends on a structural characterization of such permutations in terms of a new notion of almost-decomposability. In particular, our enumeration verifies half of a conjecture of Claesson, Jelínek and Steingrímsson, according to which avkn(1324)≤avkn+1(1324) for all n and k. Proving also the other half would improve the best known upper bound for the exponential growth rate of the number of 1324-avoiders from 13.5 to approximately 13.002.

Ort, förlag, år, upplaga, sidor
The Electronic Journal of Combinatorics, 2025
Nationell ämneskategori
Diskret matematik
Identifikatorer
urn:nbn:se:kth:diva-370692 (URN)10.37236/13387 (DOI)001567694400001 ()2-s2.0-105016015807 (Scopus ID)
Anmärkning

QC 20250930

Tillgänglig från: 2025-09-30 Skapad: 2025-09-30 Senast uppdaterad: 2026-03-31Bibliografiskt granskad
2. Towards inversion monotonicity for 1324
Öppna denna publikation i ny flik eller fönster >>Towards inversion monotonicity for 1324
(Engelska)Manuskript (preprint) (Övrigt vetenskapligt)
Abstract [en]

A collection B of patterns is called inversion monotone if the number of B-avoiding permutations of length n with k inversions is weakly increasing in n for any fixed k. Claesson, Jelínek and Steingrímsson (2012) conjectured that the pattern 1324 is inversion monotone, implying a new upper bound for its Stanley--Wilf limit. We make progress on the conjecture by proving that {1324, 231} and {1324, 2314, 3214, 4213} are inversion monotone via explicit injections. The latter follows from a general procedure for constructing inversion-monotone sets. These are the first proofs of inversion monotonicity in nontrivial cases.

A key feature of the inv-distribution on the 1324-avoiders is the limit sequence: the number of 1324-avoiding permutations of length n with k inversions is known to be constant in n when n is large. We characterize the sets of patterns for which limit sequences exist, and determine the limit sequences for all pairs {1324, p}, where p is a pattern of length four. Connections to various families of integer partitions arise.   

Finally, we expand on work by Linusson and Verkama (2025) on almost decomposable permutations to determine a broad family of sets containing 1324 that are inversion monotone under the assumption n ≥ (k + 7)/2. The method yields an enumeration of the {1324, 1342}-avoiding permutations of length n with k inversions when n ≥ (k + 7)/2.

Nationell ämneskategori
Diskret matematik
Identifikatorer
urn:nbn:se:kth:diva-378949 (URN)
Projekt
Inversions in the 1324-avoiding permutations
Forskningsfinansiär
Vetenskapsrådet, 2022-03875
Anmärkning

QC 20260401

Tillgänglig från: 2026-03-31 Skapad: 2026-03-31 Senast uppdaterad: 2026-04-01Bibliografiskt granskad

Open Access i DiVA

fulltext(1043 kB)822 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 1043 kBChecksumma SHA-512
48fb75ddffe2828ebb1ad35bb9b44f9255f3b6bb019b1661d25351adb9d17eb098f39c85ca763b4889d32f5f78bfbda23409b6e606cb6e5055c12c65774df008
Typ fulltextMimetyp application/pdf

Person

Verkama, Emil

Sök vidare i DiVA

Av författaren/redaktören
Verkama, Emil
Av organisationen
Algebra, kombinatorik och topologi
Diskret matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 822 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

isbn
urn-nbn

Altmetricpoäng

isbn
urn-nbn
Totalt: 8868 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf