Strongly regular graphs, I

Strongly regular graphs

Strongly regular graphs "stand on the cusp between the random and the highly structured", says combinatorialist Peter Cameron.  The conditions for the existence and the construction of strongly regular graphs provides a rich source of mathematical investigation, with many applications to algebra, linear algebra and combinatorics.

A graph is regular if every vertex has the same degree.  Let's use the letter k for the degree of our regular graph.

A regular graph is strongly regular if the number of walks of length 2 between two different vertices depends only on the adjacency of the two vertices.  We let  lambda  count the number of paths of length 2 between adjacent vertices and set  mu  as the number of paths of length 2 between non-adjacent vertices.

Given adjacent vertices x and y (in the figure below), the parameter  lambda  counts the number of vertices z adjacent to both.

But if x and y are not adjacent (below), mu counts the number of vertices z in this second configuration.

The parameters of a k-regular graph on v vertices are written as a 4-tuple (v, k, lambda, mu).  The graph below, on 9 vertices, with degree 4, is an example of a (9, 4, 1, 2) strongly regular graph (SRG.)  Each edge (adjacent pair) is on exactly 1 triangle, but each nonadjacent pair form the opposite corners of a 4-cycle and so there are mu=2 walks of length two between the nonadjacent vertices.

The Petersen graph, below, is an example of a (10, 3, 0, 1) SRG.

It is possible for mu and lambda to be equal.  Here (below) is the Shrikhande graph, an SRG with parameters (16, 6, 2, 2).  (This graph was found by S. S. Shrikhande.  I was privileged to work for some time at Central Michigan University with Mohan Shrikhande, son of S. S. Shrikhande.  Both father and son live in Mt. Pleasant, Michigan.)

There is (of course) a nice Wikipedia article on SRGs.  The drawing, above, have been copied from that article.

Fundamental existence question & conditions

A fundamental question in the study of strongly regular graphs is simply, "For which parameters (v, k,  lambda, mu) does there exist a SRG?"  The current progress on this question can be summarized in the tables kept by Andries Brouwer in Eindhoven, Netherlands.  

One first step to eliminating false parameter sets is the "First feasibility condition" created by counting ordered pairs of vertices (y, z) in the configuration below.

We fix the vertex x and count vertices y, z where x and y are adjacent, as are y and z, but x is not adjacent to z.  Given x, there are k choices for the vertex y and then k-lambda-1 choices for z.  (There are k vertices adjacent to y but one of those is x and there are another lambda which are adjacent to x.  Throw those out....)  So, given x, there are k(k-lambda-1) configurations like that, above.

On the other hand, given x, we can hunt for vertices z first -- there are v-k-1 choices for z -- and then hunt for y -- there are mu choices for y once we find z and so there are (v-k-1)mu  configurations like that, above.

Since we got two results for the same count, we know they must be equal and so we have the following condition on the parameters (v, k, lambda, mu) of a SRG:

k(k-lambda-1) = (v-k-1)mu

This is the "first feasibility condition" for SRGs.  There are a few more feasibility conditions, involving more subtle arguments.  We will explore two of those in a later post.

Open parameter sets

Meanwhile, just so one realizes that there are LOTS of open questions on strongly regular graphs, we mention a few "existence" questions here.  It would be very nice to either construct or rule out SRGs with the following parameters:

(65, 32, 15, 16)

(69, 20, 7, 5)

(75, 32, 10, 16)

...

(96, 35 10, 14)

(96, 45, 24, 18)

(99, 14, 1, 2)

(100, 33, 8, 12)

...

(120, 35, 10, 10)

...

(144, 52, 16, 20)

...

(160, 54, 18, 18)

(162, 21, 0, 3)

...

Of the many open cases, I have pulled out in the list above, the parameters that I (and others) find most interesting.  Most of these cases are quite hard and the discovery of a single graph in the list above would be a publishable paper!  (Write me!  Did I mention my Erdos number is 2?!)

All strongly regular graphs on 64 or fewer vertices have been found by exhaustive computer search by Ted Spence.  One might note that there are exactly 32548 distinct (nonisomorphic) graphs with parameters (36,15,6,6).

I have worked pretty hard on the parameter set (99,14,1,2).  A doctoral dissertation in computer science by Majid Behbahani (2009, here in pdf) attempts the most obvious constructions for this strongly regular graph and does not find it.  This does not rule out this SRG but makes it clear that a construction will be somewhat unusual.  In the same vein, Makhnev and Nosov describe a search for the graph (162,21,0,3).   I've also looked into (120,35,10,10) and (160,54,18,18); in both cases there is no abelian Cayley graph with these parameters.  (More on that later.)  

A strongly regular graph with parameters (3250,57,0,1) is an example of a Moore graph.  Many of us in algebraic combinatorics have looked for that graph and it still eludes us.

It turns out that the most powerful tools for the study of strongly regular come from linear algebra.  That will be the subject of the next post.

Next time: The MERiT conference & undergraduate research.

[Mathematical prerequisites: This article requires a basic introduction to graph theory.]

Follow Ken W. Smith on Twitter @kenwsmith54