proefschrift Guus Regts

Guus Regts
Guus Regts

Lex Schrijver
Lex Schrijver

boek Lovasz

Guus Regts in de verdediging

Pas gepromoveerden brengen hun werk onder de aandacht.

Redacteur: Geertje Hek
G.M.Hek at uva.nl

Eerder verschenen in Nieuw Archief voor Wiskunde, maart 2014, pp.26-27.

Graph Parameters and Invariants of the Orthogonal Group
       Guus Regts

Op 22 november 2013 promoveerde Guus Regts aan de Universiteit van Amsterdam bij prof.dr. Lex (Alexander) Schrijver op het proefschrift Graph Parameters and Invariants of the Orthogonal Group. Hij werkte de afgelopen vier jaar aan het CWI, waar de sfeer altijd goed was, zodat werken niet echt als werken aanvoelde. Het leven als oio beviel dan ook goed, ook vanwege de congressen in het buitenland die het mogelijk maakten nieuwe mensen en landen/steden te leren kennen. Toen hij pas negen maanden in dienst was werd zijn dochter geboren, het absolute hoogtepunt van de afgelopen vier jaar. Regts genoot dan ook van de mogelijkheid om zijn eigen tijd in te delen en zo een dag in de week met haar thuis te kunnen zijn.

Snijvlak van algebra en combinatoriek

Zijn proefschrift gaat over verbanden tussen graafparameters en de invariantentheorie van de orthogonale groep en enkele van haar ondergroepen. Deze verbanden worden gegeven door zogenaamde partitiefuncties van lijnkleuringmodellen. Lijnkleuringmodellen zijn generalisaties van het Ising-Potts model uit de statistische mechanica en werden geïntroduceerd als graafparameters door De la Harpe en Jones in 1993. Het werk van Regts ligt op het snijvlak van algebra en combinatoriek; aan de ene kant gebruikt hij technieken uit de algebra (en algebraïsche meetkunde) om stellingen over graafparameters te bewijzen en aan de andere kant worden grafen en andere combinatorische objecten gebruikt om meer inzicht te krijgen in bepaalde algebraïsche structuren.
       Zijn onderzoek is gemotiveerd door recente resultaten op het gebied van graaflimieten, een vrij nieuwe tak in de (discrete) wiskunde, waarover in 2012 een boek verscheen van de hand van László Lovász.

Lijnkleuringmodellen

Gegeven een graaf G, kan men de lijnen (of kanten) van G kleuren met k kleuren. Dit hoeft geen propere kleuring te zijn, d.w.z. lijnen die elkaar ontmoeten in een punt u van G mogen dezelfde kleur hebben. Stel iedere kleur voor door een element van {1,...,k}. In een punt u van G geven de kleuren van de lijnen die u bevatten dan een multideelverzameling van {1,...,k} die wordt geïdentificeerd met een element van Nk. Een k-kleur lijnkleuringmodel h is nu een afbeelding h : NkC die hieraan een complex getal toekent. Door het product te nemen over alle punten in de graaf van deze getallen krijgen we een nieuw complex getal, welke het gewicht van de kleuring genoemd wordt. In de statistische mechanica wordt dit het Boltzmann gewicht genoemd. De partitiefunctie van h, ph, is de graafparameter die aan een graaf het getal toekent dat verkregen wordt door de gewichten te sommeren over alle kleuringen van de lijnen:

partitiefunctie

Karakterisatie van graafparameters

In zijn proefschrift karakteriseert Regts welke graafparameters partitiefuncties zijn van lijnkleuringmodellen, in termen van een oneindig aantal vergelijkingen van de vorm λ1f(G1) + ... + λnf(Gn) = 0 voor zekere nN, λi∈{1,–1} en grafen Gi. Deze vergelijkingen kunnen beschouwd worden als een combinatorische interpretatie van een ideaal in een polynoomring R met een oneindig aantal variabelen. In het bewijs van de karakterisatie gebruikt Regts de Nullstellensatz van Hilbert en de eerste en tweede hoofdstelling van de invariantentheorie voor de orthogonale groep.
       Een belangrijk hulpmiddel zijn zekere gemarkeerde grafen, die fragmenten genoemd worden. Voor een lijnkleuringmodel h kan men een afbeelding definiëren van de ruimte van formele lineaire combinaties van fragmenten naar de tensoralgebra,
fragmentafbeelding
In Regts' proefschrift wordt bewezen dat over R het beeld van die afbeelding precies de deelalgebra van de tensoralgebra is die gegeven wordt door de tensoren die invariant zijn onder de ondergroep van de orthogonale groep die h stabiliseert. Over C is de situatie ietwat gecompliceerder, maar wordt een vergelijkbare stelling bewezen.
       De partitiefunctie van een puntkleuringmodel is eenzelfde soort uitdrukking als (1), alleen wordt de rol van punten en lijnen omgedraaid (dus de som is over het aantal kleuringen van de punten van de graaf). Deze partitiefuncties zijn generalisaties van het aantal homomorfismen in een vaste graaf H.
       Gebruikmakend van geavanceerde meetkundige invarianten-theorie karakteriseert Regts voor welke puntkleuringmodellen hun partitiefuncties gelijk zijn aan de partitiefunctie van een lijnkleuringmodel over R.

Compacte baanruimtes in Hilbertruimtes

Gemotiveerd door de theorie van graaflimieten wordt in het laatste hoofdstuk een stelling bewezen die aangeeft hoe je de ruimte van G-banen in de eenheidsbal van een Hilbertruimte (waar G een ondergroep is van de groep van orthogonale transformaties van de Hilbertruimte) van een pseudometriek kunt voorzien waarmee deze ruimte compact wordt. Gebruikmakend van deze stelling wordt een start gemaakt met het bestuderen van limieten van lijnkleuringmodellen.
       Zijn stelling over compacte baanruimtes in Hilbertruimtes is zeer algemeen en Regts verwacht dat daar wel mooie toepassingen uit te halen zijn. In het bijzonder staan er al twee toepassingen in zijn proefschrift en denkt Regts dat hij er nog een andere (reeds bestaande) stelling eenvoudig mee kan bewijzen.

Diverse ervaringen

Het compleet vastzitten met een probleem vindt Regts niet altijd even leuk; het gevoel dat je na een week werken niets bent opgeschoten is soms best demotiverend. Gelukkig staan daar vaak uiteindelijk momenten van inzicht tegenover die het harde werken weer de moeite waard maken: één van zijn leukste ervaringen was dat hij na wekenlang vrij vruchteloos te hebben nagedacht eindelijk op de juiste manier naar een probleem keek en toen meteen de stelling kon opschrijven en bewijzen. Wel jammer was dat daarna het resultaat vrij triviaal leek en hij zich afvroeg waarom het nodig was om er zo lang over na te denken.
       Het afronden van zijn proefschrift kostte Regts veel moeite, in het bijzonder het zetten van de puntjes op de spreekwoordelijke i en het polijsten van de tekst. Inmiddels is hij met hernieuwde energie als post-doc begonnen bij Lex Schrijver aan de UvA. In die twee jaar hoopt hij een beter beeld te krijgen van een eventuele toekomst als onderzoeker of een toekomst in een geheel andere branche.