Friday, September 14, 2007 



Width Parameters of Graphs and Codes, and Tree Tensor Networks 

In this talk we will consider recent results, where we find that
certain problems in graph theory can be linked to problems in quantum
information theory (QIT), and that mathematical techniques recently
developed in QIT can subsequently be used to investigate the initial
graph problems. We will focus on polynomials associated with graphs
and codes, such as the Tutte polynomial and weight enumerators. We show that
these polynomials can be reformulated in terms of inner products between large
tensors, and that this reformulation allows one to use the mathematical
machinery of QIT in order to study the properties of these polynomials. The
techniques involve multilinear algebra, stabilizer groups and tree tensor
networks in particular. We show that this approach leads to an efficient
algorithm to evaluate weight enumerators and the Tutte polynomial for all
graphs and codes of bounded branchwidth (thereby rederiving known results).
