Solution to the Clebsch puzzle

Here is the solution to the puzzle about the Clebsch graph I posed at the weekend. Since Gordon and Tony (and probably others) have already solved it, I am giving you my solution now.

The puzzle was:

Suppose we delete the edges of two edge-disjoint Clebsch graphs from K16. What can we say about the graph formed by the remaining edges?

It is known that the edge set of the complete graph can be partitioned into three Clebsch graphs. As observed by Greenwood and Gleason, since Clebsch is triangle-free, this shows that we can colour the edges of the complete graph with three colours so that no monochromatic triangles are created, thereby demonstrating that the corresponding Ramsey number is 17 (it is not hard to show that with 17 vertices we necessarily create a monochromatic triangle). So, if you said, “The graph could be a Clebsch graph”, you would not be wrong …

But the answer to the puzzle is that the complement of two copies of the Clebsch graph is necessarily a third copy of the Clebsch graph!

Here is why.

By standard techniques for strongly regular graphs, the eigenvalues of the adjacency matrix of the Clebsch graph are 5 (multiplicity 1, corresponding to the all-1 vector), 1 (multiplicity 10), and −3 (multiplicity 5). Suppose we have two edge-disjoint Clebsch graphs, with adjacency matrices A and B, and let C be the adjacency matrix of the graph formed by the remaining edges, so that A+B+C+I = J, where I is the identity matrix and J the all-1 matrix.

Now each of A and B has a 10-dimensional space of eigenvectors with eigenvalue 1, inside the 15-dimensional space orthogonal to the all-1 vector. These must intersect in a 5-dimensional space. Since the eigenvalues of I and J on this space are 1 and 0 respectively, the matrix equation shows that the vectors in the space are eigenvectors of C with eigenvalue −3. So C has eigenvalue −3 with multiplicity 5, in addition to the simple eigenvalue 5 corresponding to the all-1 vector.

Let r1,…,r10 be the remaining eigenvalues of C. Since the trace of C is 0 and the trace of C2 is 80 (twice the number of edges), we see that

r1+…+r10 = 10,
r12+…+r102 = 10.

So we have

(r1−1)2+…+(r10−1)2 = 0.

So r1 = … = r10 = 1.

Thus the graph C has the same eigenvalues as the Clebsch graph, and so is also strongly regular (16,5,0,2). But it is easy to see that the Clebsch graph is characterised by its parameters. (The valency is 5, and any vertex not joined to a fixed vertex * is joined to two neighbours of *; there are 10 such vertices and 10 pairs from 5, so this is a bijection. Now the induced subgraph on non-neighbours of * has valency 3, and two adjacent non-neighbours must be disjoint since otherwise a triangle is created; since there are only three pairs disjoint from a given one, everything is forced.)

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in Uncategorized and tagged , , . Bookmark the permalink.

One Response to Solution to the Clebsch puzzle

  1. The proof actually shows that two disjoint Clebsch graphs are part of an association scheme.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s