Växande delföljder i lokalt likformiga slumppermutationer

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?