Slumpmässiga nätverk under lupp

Docent Cecilia Holmgren får anslag av Knut och Alice Wallenbergs Stiftelse, till en postdoktoral tjänst för att rekrytera en forskare från utlandet till Matematiska institutionen, Uppsala universitet.

Projektet studerar viktiga problem inom de matematiska områdena sannolikhetsteori och kombinatorik. Forskargruppen studerar framförallt slumpmässiga grafer och träd.  Detta är nu ett av de mest dynamiska fälten i matematik på grund av dess många intressanta ”rena” matematiska frågor och dess viktiga tillämpningar inom t.ex. datavetenskap, fysik och biologi.

En graf består av punkter, hörn, där vissa hörn är parvis hopbundna med kanter. Två hörn

är grannar om de är förbundna med en kant. Om hörnen binds ihop på ett slumpmässigt sätt bildas slumpgrafer. En viktig del av projektet gäller slumpträd, vilka påminner om vanliga släktträd. Många slumpträd kommer från datavetenskap där de bland annat används för att studera sökalgoritmer.

Splitträd omfattar en stor klass av slumpträd. De konstrueras genom att man delar ut ett visst antal objekt (som oftast symboliserar data) till hörnen med hjälp av en slumpprocess. Det mest kända splitträdet är Quicksort, en av de viktigaste sökalgoritmerna som används för att snabbt hitta och sortera data. En viktig frågeställning i projektet är att analysera i vilken utsträckning vissa typer av delträd så kallade kantträd kan ge kunskap om hela trädets struktur för olika typer av splitträd.

En annan del av projektet handlar om fasövergångar hos slumpmässiga processer som förekommer inom området perkolation. Projektet är särskilt fokuserat på bootstrap perkolation. Detta är en process på grafer som kan liknas av hur en smitta sprids i en population. I denna modell representerar varje hörn en individ som är eller inte är smittad. En individ blir smittad om den har ett visst antal smittade grannar. Modellen gör det möjligt att följa sjukdomsspridningen beroende på vilka individer som smittats först. I projektet studeras bl.a. tiden det tar för att alla individer i grafen ska smittas.

Projektet behandlar också slumpmässiga nätverk som kan representeras med slumpgrafsmodeller bl.a. konfigurations-modellen. För ett sådant nätverk studeras sannolikheten för att en korrekt slumpgraf ska kunna konstrueras så att den inte innehåller någon “self-loop”, d.v.s. någon koppling som går tillbaka till hörnet själv och inte heller några multipla kanter mellan två hörn.

Foto: Uppsala universitet