Text

Komplexa inbyggda system i realtid

Learning, Inclusive education, School transitions – for All (LISA)

M-TERM - Mälardalen University Team of Educational Researchers in Mathematics

Programvarutestlaboratorium

Redovisning och ekonomistyrning

Space and Place in Early Childhood Education and School (SPiECES)

Stokastiska processer, statistik och finansmatematik

Teknisk matematik

Tillförlitlig programvaruteknik

Algebra och Analys med tillämpningar

Artificiell intelligens och intelligenta system

Automatiserade mjukvaruspråkutveckling och mjukvaruteknik

Beteendemedicin, hälsa och levnadsvanor

Certifierbara bevis och justifieringsteknik

Digitalisering av framtidens energi

Diskret matematik och modellering av beteende och kultur

Formell modellering och analys av inbyggda system

Industriell programvaruteknik

Växande delföljder i lokalt likformiga slumppermutationer

Syftet är att öka förståelsen för strukturen hos växande delföljder i slumppermutationer. Detta är ett naturligt steg mot det större målet att skapa en teori för slumppermutationer i analogi med den rika befintliga teorin för slumpgrafer.

Start

2021-07-01

Planerat avslut

2024-12-31

Huvudfinansiering

Forskningsinriktning

Projektansvarig vid MDU

No partial template found

Bakgrund

Detta projekt handlar om slumppermutationer, det vill säga slumpmässiga ordningar av talen 1 till n, som till exempel 247951368 om n är 9. En växande delföljd i en permutation är en delmängd av talen som står i rätt ordning, till exempel 2,4,5,6,8 i vår exempelpermutation. Studiet av den maximala längden hos en växande delföljd i en slumppermutation har en lång historia med många oväntade kopplingar till andra delar av matematiken. Det finns också tillämpningar utanför matematiken, till exempel bordning av flygplan: I kön vid gaten står resenärerna i nästan slumpmässig ordning. Vad är det som avgör hur smidigt bordningen går? Jo, långa delföljder i kön som är växande med avseende på stolsnumren är bra för effektiviteten, för de resenärerna står i rätt ordning och behöver inte passera varandra i planets mittgång.

Det nya i detta projekt är att jag även vill studera delföljdernas positioner i slumppermutationen. Närmare bestämt är jag intresserad av positionerna för en maximal union av ett givet antal växande delföljder, det vill säga växande delföljder som tillsammans innehåller så många av talen som möjligt. I vår exempelpermutation finns det två växande delföljder som tillsammans innehåller åtta av de nio talen, nämligen 2,4,7,9 tillsammans med 1,3,6,8, och detta är det mesta som går att uppnå med två delföljder.

Ett mål med projektet är att beskriva hur dessa maximala unioner av växande delföljder beter sig asymptotiskt då n går mot oändligheten. En annan ny aspekt har att göra med hur slumppermutationerna genereras. Lejonparten av forskning kring slumppermutationer begränsar sig till den likformiga fördelningen där varje möjlig permutation är lika sannolik. Jag vill tillåta även vissa olikformiga fördelningar i min analys, och det är det andra målet i projektet.


Syfte

Syftet är att öka förståelsen för strukturen hos växande delföljder i slumppermutationer. Detta är ett naturligt steg mot det större målet att skapa en teori för slumppermutationer i analogi med den rika befintliga teorin för slumpgrafer.

 

Aktiviteter

Planen är att först undersöka slumppermutationer som genereras av en poissonprocess i diamanten |x| + |y| < 1 och antagligen använda någon typ av subergodisk sats för att visa existensen av gränsstorlekar hos unioner av växande delföljder. Sedan, genom att klistra ihop flera omskalade och translaterade versioner av diamanten, hoppas vi att kunna hantera slumppermutationer som genereras av en inhomogen poissonprocess i ett allmänt område.

 

Projektmål

Målet är att svara på följande frågor:

  1. För stora n och konstant r, var i permutationsdiagrammet finns typiskt den maximala unionen av r sqrt(n) växande delföljder?
  2. Vad händer om permutationen inte är likformigt utan endast lokalt likformigt slumpmässig?