Semidefine Programming in Algebraic Combinatorics

In the seventies, Philippe Delsarte in a seminal work developed a method in Algebraic Combinatorics that yields upper bounds for the cardinality of codes with given minimal distance as a solution of a linear program. This method, also called the Delsarte method, or polynomial method, was developed in the framework of Association Schemes , which is the most general framework dealing with finite metric spaces.This method also obtains bounds in more general situations, such as lower bounds for designs (combinatorial and spherical). To be brief, it translates problems in finite metric spaces enjoying a great degree of symmetry and/or regularity (like the Hamming scheme for codes of the Johnson schemes for designs) into spectral problems of linear algebra. These problems, in turn, can be approached by use of special functions and especially certain systems of orthogonal polynomials of one discrete variable ( Krawtchouk polynomials for codes and Hahn polynomials for designs) and the extremal properties of their zeroes. The algebra of matrices that occurs in this context is the Bose-Mesner algebra. Since the nineties, another algebra of matrices attached to association schemes has been under much study : the Terwilliger algebra. Semidefinite programs (SDP for short) constitute a special family of optimization problems which have recently become amenable to solution in polynomial time. New algorithms, based on interior point methods, have reasonable efficiency in practice. Semidefinite programs contain linear programs as a special class. More precisely, an SDP is expressed in the following way: let A0,A1, . . . ,An be real symmetric matrices, and b1, . . . , bn real numbers. One wants to find the minimum of the objective function b1x1 + . . . + bnxn over the convex set defined by the condition: A0 + x1A1 + . . . + xnAn ≥ 0, where the notation A ≥0 means that the eigenvalues of the symmetric matrix A are nonnegative. SDP formulations for certain combinatorial optimization problems have been known for decades; thus the new algorithms yield polynomial time solvable relaxations for some notoriously hard problems related to graph invariants. We have already mentioned the 1 stability number of a graph; the colouring number, the maximal size of a cut are also relevant examples. One of the main contributions in this area is due to L. Lovász, who introduced the so-called theta number of a graph. This number is obtained by the optimal value of an SDP, and provides an upper bound on the stability number. With this number, Lovász proved Shannon’s conjecture on the capacity of the pentagon. Quite recently, by moving from LP to SDP, a number of new results and ideas have been developed in the domain of sphere packings, and these are of course the topics we want to focus on during the summer school. We believe that they open new directions that may be fruitfully explored by young people in the future.