Connection Matrices, Homomorphisms, and Edge Coloring Models
Suppose you want to evaluate a graph parameter on a graph. There is a (node- or edge-)cut in the graph, and while you know everything about one side of the cut, you have to pay for information about the other side. How much information do you need about the other side? Under appropriate conditions, the answer can be characterized as the rank of a matrix, the "connection matrix". Other properties of this matrix, like whether or not it is semidefinite, also turn out to have graph theoretic significance, in particular, they can be used to characterize homomorphism functions, "edge-coloring" functions, and limits of graph sequences.
This is a report on joint work with Michael Freedman, Lex Schrijver, Balazs Szegedy and Dominic Welsh.
Lászlo Lovász, Eotvos Lorand University and Microsoft Corporation
