# Connection between graph theory and algebra deepened

Publication date: 28-11-2013

PhD student Guus Regts from Centrum Wiskunde & Informatica (CWI) investigated mathematical connections between graph theory and algebra. On 22 November he defended his PhD thesis 'Graph Parameters and Invariants of the Orthogonal Group' at the University of Amsterdam. His research is closely related to the young field of graph limits, a research area in which researchers try to understand extremely large networks in a fundamental way. In the future, results might be used as input for modelling social networks like Facebook and other large networks – such as the human brain, internet, and chip design.

In maths, a network of points and lines is called a graph. With millions or even billions of points connected, researchers are not only able to look at graphs in detail, but they can also zoom out to explore larger structures. Regts investigated properties that became visible on a larger scale, such as the density of small graphs in a large graph. He also investigated edge colouring models, which are used in statistical mechanics to study phase transitions.

The PhD student deepened the known connection between graph parameters and the 'invariants theory of the orthogonal group' from algebra, a classical branch of mathematics that was initiated by the renowned mathematician Hilbert. Together with CWI Fellow Lex Schrijver, Guus Regts proved a theorem from which the existence of graph limits and limits of edge colouring models can be derived.

The fundamental research was funded by the Spinoza Prize from Lex Schrijver. Guus Regts: “Working with Lex Schrijver was really inspiring. He knows how to look at a problem in the right way, and how to tackle it. I think it is important that fundamental research is being funded. You don’t know what will be discovered, and sometimes you will just find the detour that was necessary to solve a major problem.

The research has been carried out at the Centrum Wiskunde & Informatica (CWI) in Amsterdam. CWI is related to the Netherlands Organisation for Scientific Research (NWO).

More information: http://www.cwi.nl/research-groups/Networks-and-Optimization

PhD thesis: http://dare.uva.nl/record/458946

*Picture: Guus Regts (CWI)*