Two-Graphs

The problem that we are about to discuss is one of the founding problems of algebraic graph theory, despite the fact that at first sight it has little connection to graphs. A simplex in a metric space with distance function d is a subset S such that the distance d(x, y) between any two distinct points of S is the same. In ℝd, for example, a simplex contains at most d + 1 elements. However, if we consider the problem in real projective space then finding the maximum number of points in a simplex is not so easy. The points of this space are the lines through the origin of ℝd, and the distance between two lines is determined by the angle between them. Therefore, a simplex is a set of lines in ℝd such that the angle between any two distinct lines is the same. We call this a set of equiangular lines. In this chapter we show how the problem of determining the maximum number of equiangular lines in ℝd can be expressed in graph-theoretic terms.