Symmetric Powers of Graphs
Let X be a graph on n vertices with vertex set V(X) and edge set E(X). Then the k'th symmetric power X{k} is the graph with the C(n,k) k-subsets of V(X) as vertices with two such k-subsets adjacent if their symmetric difference is in E(X). For convenience we use the terms symmetric square and symmetric cube for X{2} and X{3} respectively.
As an example, the following pictures show the symmetric square of the 5-cycle C5.
Every edge of any symmetric power of a graph X is naturally associated with an edge of X itself, namely the symmetric difference of its endpoints. In the symmetric square each set of edges associated with a single edge of X contains n-2 independent edges. If we assume that the edges of C5 are coloured red, blue, green, cyan and purple (in cyclic order), then the associated colouring of C5{2} is shown in the second picture.
We are interested in the spectral properties of the symmetric powers of graphs, or more precisely in the spectral properties of their adjacency matrices (although we can consider the same questions for other matrices, such as the Laplacian).
In general, we would expect that for any fixed k there should be an infinite number of pairs of graphs with cospectral symmetric k'th powers and in fact we know a large number of pairs of graphs with cospectral symmetric squares, but currently we do not even know of even one pair of graphs with cospectral symmetric cubes.
Strongly Regular Graphs
Recall that a graph X is strongly regular with parameters (n,k,a,c) if
- X has n vertices,
- X is regular with degree k,
- Every two adjacent vertices have a common neighbours, and
- Every two (distinct) non-adjacent vertices have c common neighbours.
A strongly-regular graph X is primitive if both X and its complement are connected, and we normally assume (often silently) that this is the case to avoid obfuscating every theorem with the addition of uninteresting special cases.
Strongly regular graphs have strong spectral properties including the fact that the eigenvalues of their adjacency (and Laplacian) matrices are determined solely by the parameters (n,k,a,c) and are independent of the structure of the graph. In particular, for appropriate choices of the parameters, we can find large collections of pairwise non-isomorphic cospectral graphs.
Chris Godsil has demonstrated that any two strongly-regular graphs with the same parameters have cospectral symmetric squares and so one might hope that some of these graphs would also have cospectral symmetric cubes.
The following table shows the exact numbers of strongly-regular graphs of all sizes up to 36 vertices.
| Parameters | Number of known SRGS |
|---|---|
| (5, 2, 0, 1) | 1 |
| (9, 4, 1, 2) | 1 |
| (10, 3, 0, 1) | 1 |
| (13, 6, 2, 3) | 1 |
| (15, 6, 1, 3) | 1 |
| (16, 5, 0, 2) | 1 |
| (16, 6, 2, 2) | 2 |
| (17, 8, 3, 4) | 1 |
| (21, 10, 3, 6) | 1 |
| (21, 10, 5, 4) | 1 |
| (25, 8, 3, 2) | 1 |
| (25, 12, 5, 6) | 15 |
| (26, 10, 3, 4) | 10 |
| (27, 10, 1, 5) | 1 |
| (28, 12, 6, 4) | 4 |
| (29, 14, 6, 7) | 41 |
| (35, 16, 6, 8) | 3854 |
| (36, 10, 4, 2) | 1 |
| (36, 14, 4, 6) | 180 |
| (36, 14, 7, 4) | 1 |
| (36, 15, 6, 6) | 32548 |
Note: All of these graphs are available from Ted Spence's page of strongly-regular graphs.
The smallest pair of cospectral strongly-regular graphs has 16 vertices and so their symmetric squares have 120 and 560 vertices respectively, which are already approaching the limits of many computer packages for calculating exact characteristic polynomials over the integers. The graphs on 36 vertices have symmetric squares with 630 vertices and symmetric cubes with 7140 vertices, with this last size exceeding the capacity of any widely-distributed software for calculating exact characteristic polynomials over the integers.
As the adjacency matrices of the symmetric cubes are sparse and symmetric, they are (relatively) amenable to numerical calculation of eigenvalues, and Terry Rudolph and his colleagues have used Matlab to verify that there are no pairs of strongly-regular graphs with 29 vertices or fewer that have cospectral symmetric cubes.
Incidence Graphs
Recall that a 2-(v,k,l) design D consists of a set of size v called the points of D together with a collection of k-sets of points called the blocks of D such that every pair of distinct points lies in exactly l blocks.
The incidence graph I(D) of a design D is the bipartite graph whose vertices are the points and blocks of D and where two vertices are adjacent if and only if they form an incident point/block pair.
We consider the symmetric squares of various small designs, only considering those parameter sets for which at least two non-isomorphic designs exist.
| Design | v+b | Number | Char. pol of I(D) | Char. pol of I(D){2} |
|---|---|---|---|---|
| 2-(13,3,1) | 13+26 | 2 |
(x)13 (x2-18) (x2-5)12 |
(x)197 (x2-20)40 (x2-5)131 (x4-74x2+360) (x6-37x4+376x2-648)13 (x10-73x8+1673x6-14489x4+44528x2-41080)12 |
| 2-(7,3,2) | 7+14 | 4 |
Data
In this section, we provide access to the adjacency matrices of the symmetric cubes in Jean Guillaume-Dumas' SMS format. However, we are forced to do this in an indirect fashion because even when compressed with gzip, the matrix for the symmetric cube of each 35-vertex strongly-regular graph occupies 800K, which would result in a total download size of 3.1Gb for all 3854 matrices.
Therefore, the following file(s) contain the adjacency matrices of the original strongly-regular graphs, together with a Java program for computing the adjacency matrix of the symmetric cube of any one of them which is then printed out in SMS format. Although the Java program is relatively slow, it is easy to check that it cannot accidentally (or maliciously) corrupt anything on your computer.
To use the data and program on, for example, the file of (35, 16, 6, 8) SRGs, proceed as follows:
- Get data
Download the compressed file of SRGs and uncompress it, resulting in
srg35. - Get program
Download the Java file, and compile it: all that is needed is
javac SRMatrix.java - Compute a matrix
Run the Java program using the syntax
java SRMatrix srg35 35 numwherenumis a number from 1 to 3854 indicating which of the SRGs you wish to process, and the corresponding matrix will be printed to the standard output. (Currently there is no mechanism in the program to process multiple lines.)