Graph parameters and invariants of the orthogonal group

This thesis is concerned with links between certain graph parameters and the invariant theory of the orthogonal group and some of its subgroups. These links are given through so-called partition functions of edge-coloring models. These partition functions can be seen as graph parameters as well as polynomials that are invariant under a natural action of the orthogonal group. As graph parameters they may be seen as generalizations of counting the number of line-graph homomorphisms.

In Chapter 5 of this thesis we characterize which graph parameters are partition functions of complex edge-coloring models. This is done using the First and Second Fundamental Theorem from invariant theory and Hilbert’s Nulstellensatz. In Chapter 6 we give a combinatorial interpretation of algebras of tensors that are invariant under certain subgroups of the orthogonal group. Using some advanced techniques from geometric invariant theory, we characterize which partition functions of vertex-coloring models are edge-reflection positive in Chapter 7. In Chapter 8 we prove a result on compact orbit spaces in Hilbert spaces and use this to develop a limit theory of edge-coloring models.

Our results are motivated by, and connected to, the rather recent field of graph limits and graph partition functions, whose study was initiated by Borgs, Chayes, Lovász, Schrijver, Sós, Szegedy and Vesztergombi.