Hoppa direkt till innehållet

Information till studenter och medarbetare med anledning av covid-19 (Uppdaterad: 31 mars 2021)

printicon

Grafteori och algoritmer

Forskningsprojekt Inom alla vetenskaper finns olika typer av nätverk av relationer, detta kan vara allt från vägnät till nätverket av kontakter mellan en grupp personer. Inom grafteori studerar vi de egenskaper som alla nätverk får, oavsett vad de tänks modellera.

Min forskning inom grafteori rör dels strukturen hos grafer och hypergrafer, dels olika typer av sannolikhetsmodeller på grafer, samt olika beräkningsproblem med koppling till grafer och kombinatorik. Inom strukturteori är vi till exempel intresserade av hur cykler (slutna vägar) i grafer uppför sig under olika bivillkor. Till exempel har jag studerat hur många cykler en graf kan ha om den innehåller ett visst antal kanter (länkar). Ett exempel på en sannolikhetsmodell på grafer är perkolation, där man med en viss sannolikhet rycker bort kanter ur en graf och sedan är intresserad av att se vilka egenskaper den kvarvarande grafen har.

Projektansvarig

Projektöversikt

Projektperiod:

2008-05-19 2009-12-31

Medverkande institutioner och enheter vid Umeå universitet

Institutionen för matematik och matematisk statistik, Teknisk-naturvetenskaplig fakultet

Forskningsområde

Matematik

Projektbeskrivning

För tillfället är min forskning mest fokuserad på sannolikhetsmodeller på grafer, som ofta har en koppling till olika algebraiska strukturer, samt olika algoritmiska problem.

Jag arbetar till exempel med olika slumpmodeller som konstruerar grafer med hjälp av grupper eller latinska kvadrater och undersöker vilka egenskaper som de framslumpade graferna har. Ett exempel på ett nyligt resultat är en optimal version av en sats om hur god expansion en framslumpad graf baserad på en grupp har. Som en del av det arbetet utvecklade jag en metod för att visa att slumpmatriser ligger nära sina väntevärden, något som har tillämpning inom till exempel kvantkommunikationer.

Inom min algoritmiska forskning har jag å ena sidan arbetat med att rent konkret utföra storskaliga parallella beräkningar inom kombinatorisk optimering. Målet här har varit att konstruera olika typer av optimala designer och hypergrafer. Å andra sidan har jag arbetat med ren algoritmutveckling också. Inom det området har jag till exempel konstruerat en algoritm för att snabbt reducera matriser, med element från ändliga kroppar, och en relaterad algoritm för att snabbt multiplicera matriser med element från en semiring. De här två algoritmerna har tillämpningar inom knäckning av kryptosystem och exempelvis snabba sannolikhetsuppskattningar.
Nyligen har jag också börjat studera algoritmer med koppling till bioinformatik.