Linear and semi-definite programming bounds for codes in distance-regular graphs
The question of computing the size of the largest clique or independent set in a graph is famously NP-hard. Since a code in a graph is a set of vertices which is independent at several distances, it is likewise difficult to compute the maximum size of a code of a fixed minimum distance. When a graph is distance-regular, its distance graphs form an association scheme. In this setting, upper bounds on the size of cliques and codes can be computed more efficiently as the solution to a linear or semi-definite programming problem. This strategy combines techniques from algebra, combinatorics, and convex optimization to produce some of the best known upper bounds for the size of these sets. This talk will discuss some of the background of the problem, the theory of association schemes, and the linear programming bound of Delsarte and the semi-definite programming bound of Schrijver.