Sortering och smittspridning
Grafer kan användas för att beskriva och modellera många företeelser. Slumpträd visualiserar till exempel en vanlig datoralgoritm. Här ges också exempel på hur en egenskap kan spridas i en graf, vilket studeras i det som kallas perkolationsteori.
blir mer än sex steg mellan vilka slumpmässigt valda noder som helst.
– För de flesta personer är det bara tre eller fyra steg emellan, säger Cecilia Holmgren.
Det här är ett ganska begripligt exempel, som illustrerar vad forskare i grafteori får fram för typ av resultat – de hittar formler eller sannolikhetsfördelningar som beskriver egenskaperna hos olika typer av grafer. När matematikerna undersöker hur många led det är mellan två slumpmässiga personer på jorden, beräknar de hur längden mellan två noder varierar beroende på hur tätt hopkopplad grafen är – alltså hur många kontakter varje person har i genomsnitt.
När jag tittar igenom titlar och sammanfattningar på Cecilia Holmgrens vetenskapliga publikationer från de senaste åren, är de fulla av termer och uttryck som är ogenomskinliga för mig. (En av titlarna är The asymptotic non-normality of the giant cluster for percolation on random split trees.) Jag kan förstå så mycket som att det handlar om hur olika egenskaper hos graferna hänger ihop med varandra, och hur de ändras när graferna påverkas på olika sätt. Men vissa saker klarnar när Cecilia Holmgren själv berättar om dem.
Hennes arbete handlar mycket om den speciella typen av grafer som kallas träd, som det hon har ritat upp på tavlan. En speciell sak med den här typen av graf är att det bara finns en väg mellan två noder.
Slumpträd är en form av slumpgrafer. Slumpgrafer konstrueras genom att dela ut egenskaperna i grafen på ett slumpmässigt sätt: antalet noder, antalet kanter, och hur kanterna kopplar ihop noderna. Slumpträd börjar med en nod i roten, och sedan läggs grenarna till med någon slumpfaktor. Cecilia Holmgren har arbetat mycket med en klass av slumpträd som kallas splitträd. Det enklaste exemplet är något som kallas binära sökträd, som har en direkt koppling till datavetenskapen. Avståndet mellan roten och de yttersta noderna, ”löven”, på ett sökträd ger ett mått på hur effektiv den motsvarande sökalgoritmen är.
Cecilia Holmgren har bland annat jobbat med att hitta allmänna beskrivningar av hur avstånden mellan olika noder inuti alla möjliga olika typer av sådana träd utvecklas, beroende på olika parametrar.
– I min forskning är jag intresserad av att visa generella resultat som gäller för alla träd på en gång. Tidigare forskning har som regel bara studerat en typ av träd i taget, säger hon.
”Ofta går jag och tänker på mina matematiska problem även när jag inte är medveten om det och det har hänt flera gånger att jag löst viktiga problem medan jag till exempel har ridit min häst.” Cecilia Holmgren
Hon jobbar också med problem som påminner om hur rykten eller smittor sprids. Man kan markera slumpmässiga noder i en graf som ”smittade”, och sedan får smittan spridas längs kanterna till andra noder enligt någon given regel. En sådan regel kan vara att om en nod har minst två smittade grannar så blir den också smittad. Sedan undersöker man hur smittan sprids genom grafen, och hur stor del av grafen som nås.
Studiet av grafers egenskaper när man förändrar dem enligt vissa regler, som när smittan sprids, kallas på matematikspråk för perkolation. Ordet kanske känns igen från kaffebryggning, och teorin för perkolation har mycket riktigt sitt ursprung i modeller för hur vätskor kan flöda fram genom porösa material – precis som när vattnet sipprar genom de malda kaffebönorna.
Perkolationsteorin använder hon för att studera speciella fall där en liten förändring gör att slutresultatet blir helt annorlunda.
Ett exempel är sannolikheten för att ett släktnamn ska överleva eller dö ut. Det studerades först av forskarna Francis Galton och Henry William Watson på 1800-talet, som var intresserade av brittiska adelssläkter. Släkten börjar med en man, och varje familjemedlem får ett slumpmässigt antal söner som kan föra släktnamnet i arv. Det finns en sannolikhet för att släktnamnet ska överleva för evigt om medelvärdet av antalet söner per person är större än 1. Om medelvärdet är mindre än 1 dör släktnamnet alltid ut. När medelvärdet är större än 1 kan namnet leva för evigt, vilket betyder att trädet blir oändligt högt. Medelvärdet 1 av antal söner per person är alltså en brytpunkt mellan ändliga och oändliga träd.
Sådana brytpunkter för förändringar kallas för fasövergångar, i analogi med fysiken där en mycket liten ändring i tryck eller temperatur kan få ett ämne att helt ändra karaktär genom att det smälter, stelnar eller förångas.
På liknande sätt finns det också fasövergångar i spridningar av en ”smitta” i grafen. Cecilia Holmgren studerar vilka sannolikheter som behövs för att smitta en hel graf, givet olika förutsättningar. Från början låter man varje nod vara smittad med en viss sannolikhet och sedan låter man smittan spridas enligt den givna regeln. Om sannolikheten för att en nod är smittad från början är lite över ett kritiskt värde, kommer hela grafen att smittas, annars inte.
Medan vi pratar om smittor berättar Cecilia Holmgren om ett annat klassiskt problem i grafteori, som kallas för vänskapsparadoxen. Om du bara har få vaccindoser men vill skydda befolkningen så bra som möjligt – vad är bästa sättet för att fördela vaccinet?
– Det visar sig att det bästa är att fördela vaccinet slumpmässigt, men att be varje person som får vaccinet att i stället för att ta det själv ge det till en kompis. Den som får vaccin är då troligtvis en social person, som utan vaccin skulle ha spritt sjukdomen effektivt.
Att hennes forskning kom in på slumpgrafer var delvis en tillfällighet. Hon sökte sig till Uppsala för att få göra sin doktorsavhandling med professor Stefan Jansson som handledare, en av de världsledande forskarna inom ämnet slumpgrafer. Cecilia Holmgren tycker att det är en rolig och intressant del av matematiken.
– Jag gillar att det är en skärning mellan sannolikhetsteori och kombinatorik. Kombinatoriken innehåller kluriga lösningar, och sannolikhetsteorin har en djup teoretisk grund.
För en utomstående kan det vara svårt att förstå hur en matematiker arbetar. Det är inte som att gå till ett laboratorium och ställa upp ett experiment. Cecilia Holmgren berättar att hon ofta har en idé om vilka metoder hon vill försöka använda, när hon står inför ett givet problem. En del av det kommer med erfarenhet, genom att hon har lärt sig allt fler olika matematiska metoder och även att kombinera dem.
– Ändå kommer lösningar ofta när man minst anar det. Ofta går jag och tänker på mina matematiska problem även när jag inte är medveten om det, och det har hänt flera gånger att jag löst viktiga problem medan jag till exempel har ridit min häst.