[ Français ]

Graph Theory, Algebraic Combinatorics and Mathematical Physics
July 25 - August 19, 2022

This period on graphs and combinatorics will be organized in two parts that both have intimate connections with algebras and physics. The first one will focus on association schemes and the underlying algebraic structures and the second on graphs and quantum computing issues.

Association schemes and algebras

An association scheme is a combinatorial object that generalizes both a finite group and a distance-regular graph. In his 1973 thesis, Delsarte introduced two types of association schemes, said to be P-polynomial and Q-polynomial. Attached to each association scheme is a semisimple algebra called the Bose-Mesner algebra. Around 1992, Terwilliger introduced the subconstituent algebra T, which is generated by the Bose-Mesner algebra and its dual. The algebra T is finite-dimensional and semisimple. If the scheme is P-polynomial and Q-polynomial, then T is a homomorphic image of the q-Onsager algebra. This is one reason why the representation theory of the q-Onsager algebra is presently under intense study. In this representation theory the notion of a Leonard pair and tridiagonal pair play a key role. A Leonard pair consists of two multiplicity-free linear maps on a finite-dimensional vector space, that each act on the eigenspaces of the other one in a tridiagonal fashion. A tridiagonal pair is a mild generalization of a Leonard pair.

A related topic involving association schemes has to do with spin models. These statistical mechanical models were introduced in 1989 by Vaughan Jones, and used to construct invariants for knots and links. Notable early advances in this area are due to Bannai, Jaeger and Nomura. More recent work involving Jones pairs is due to Chan, Godsil, and Munemasa. Recently Caughman, Curtin, Nomura, Terwilliger, and Wolff used the subconstituent algebra to investigate association schemes whose Bose-Mesner algebra contains a spin model. An attractive open problem is to find all the spin models that are contained in the Bose-Mesner algebra of an association scheme that is P-polynomial and Q-polynomial.

Yet another topic involving association schemes has to do with the double affine Hecke algebra (DAHA). If an association scheme is P-polynomial and Q- polynomial, then each Delsarte clique induces a module for the DAHA of type (C1∨,C1) through the recent work of Jae-ho Lee. Investigating this connection is an active area of research.

Graphs and quantum computing

Quantum walks can be viewed as quantum generalization of classical random walks (which are an important tool in computer science). Quantum walks can be used as a basis for algorithms. In particular Grover’s search algorithm, one of the most important algorithms in Quantum Computing, can be implemented very naturally as a quantum walk. Quantum walks may also be used as subroutines in a quantum computer. Most of the quantum walks that have been proposed are based on graphs and this leads to a fundamental problem: what is the relation between properties of the walk and properties of the underlying graph?

The theory of quantum homomorphisms of graphs is a more recent development (with Roberson’s 2013 Ph.D thesis one of the major starting points). Classically, questions involving colourings form a central part of graph theory. They are important because of the theoretical problems they raise, and because colouring algorithms play a significant role in real world scheduling problems. However for each classical problem, there is a quantum analog, and the exact relation between the two versions is as yet only poorly understood. In a number of cases questions about quantum colourings and homomorphisms give rise to problems that can be solved by quantum protocols, but are not solvable classically. Thus they provide important information about the potential power of quantum computers.

Questions about how to maximize the information obtained from measurements of quantum states lead very naturally to questions concerning the geometry of sets of lines in complex space. It is surprising that the corresponding geometrical questions in real space reduce to combinatorial questions that form a central topic in algebraic combinatorics, and have long been studied. Similar questions are studied in analysis under the guise of “tight frames”, but the people working in this area have so far had limited interaction with physicists.