Verband tussen grafentheorie en algebra verder verdiept

Publication date: 28-11-2013


CWI-promovendus Guus Regts onderzocht wiskundige verbanden tussen grafentheorie en algebra. Op 22 november 2013 promoveerde hij op zijn proefschrift 'Graph Parameters and Invariants of the Orthogonal Group' aan de Universiteit van Amsterdam. Zijn onderzoek is nauw verwant aan het jonge vakgebied van 'graaflimieten',  een vakgebied waarin onderzoekers op een fundamentele manier grote netwerken proberen te begrijpen. In de toekomst kunnen resultaten mogelijk gebruikt worden als input voor het modelleren van social networks als Facebook en andere grote netwerken, zoals het menselijk brein, internet en chip design.

In de wiskunde wordt een netwerk van punten en verbindingen een graaf genoemd. Als miljoenen of miljarden punten door lijnen in een graaf verbonden zijn, dan kun je er er niet alleen op kleine schaal naar kijken maar ook uitzoomen, en grotere structuren bestuderen. Guus Regts onderzocht eigenschappen die op die grotere schaal zichtbaar werden, zoals de dichtheid van kleine grafen in een grote graaf. Ook onderzocht hij edge colouring modellen, die in de statistische mechanica worden gebruikt voor het bestuderen van faseovergangen.

De promovendus diepte de verbinding uit tussen graafparameters en de 'invariantentheorie van de orthogonale groep' uit de algebra, een klassieke tak van wiskunde die ooit door de beroemde wiskundige Hilbert is gestart.  Samen met CWI Fellow Lex Schrijver bewees hij een stelling waaruit de existentie van graaflimieten en limieten van edge colouring models kan worden afgeleid.

Het fundamentele onderzoek is gefinancierd door de Spinozapremie van Schrijver. Guus Regts: "Het werken met Lex Schrijver vond ik bijzonder inspirerend; hij weet hoe je een probleem op de goede manier kunt bekijken en aanpakken. Ik vind het belangrijk dat fundamenteel onderzoek wordt gefinancierd: je weet niet wat er wordt blootgelegd en soms vind je net die omweg, die nodig is om tot een oplossing van een belangrijk probleem te komen."

Het onderzoek is uitgevoerd op het Centrum Wiskunde & Informatica (CWI) in Amsterdam. CWI is gelieerd aan de Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NWO). 


Meer informatie: http://www.cwi.nl/research-groups/Networks-and-Optimization

Proefschrift: http://dare.uva.nl/record/458946

Foto: Guus Regts (CWI)