For best experience please turn on javascript and use a modern browser!
You are using a browser that is no longer supported by Microsoft. Please upgrade your browser. The site may not present itself correctly if you continue browsing.
Pas gepromoveerden brengen hun werk onder de aandacht.
Redacteur: Geertje Hek,
G.M.Hekatuva.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 :
Nk → C 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:
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 n∈N, λ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,
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.
Cookie Consent
The UvA uses cookies to ensure the basic functionality of the site and for statistical and optimisation purposes. Cookies are also placed to display third-party content and for marketing purposes. Click 'Accept all cookies' to consent to the placement of all cookies, or choose 'Decline' to only accept functional and analytical cookies. Also read the UvA Privacy statement.