Strongly regular graphs

graph is called regular if its every vertex has the same number of neighbours. For example, this is a regular graph where each vertex has exactly three neighbours:

It is the well known Petersen graph which is so important and popular in graph theory that it even has a full book devoted to it. It is probably not the first example that will come to your mind when one talks about regular graphs. Some more basic examples would be, a cycle or the trivial graph where every vertex has precisely zero neighbours. But we are going to talk about graphs that are “strongly” regular and then the Petersen graph is probably the perfect graph to start the with (even though it isn’t really perfect).

Let’s collect some obvious facts that you can observe by looking at the picture. This graph has 10 vertices, 15 edges, degree 3 and maximum distance of 2 between any pair of points. If you observe it even more carefully then you would see that there are no triangles or squares in this graph, but clearly there is a pentagon (how many of those are there?). This is the same as saying that the girth of the Petersen graph is 5Of course not all these parameters are independent. It can be easily proved that any regular graph of degree 3 and diameter (maximum distance between two points) 2 has at most 10 vertices. And when that bound is achieved then the graph must necessarily have girth 5. Therefore, Petersen graph is a maximal graph with fixed degree 3 and fixed diameter 2. In fact, it can be proved that Petersen graph is the maximal graph satisfying those conditions.

The fact that the Petersen graph has diameter 2 and girth 5 can also be written as, every pair of adjacent vertices have zero common neighbours and every pair of non-adjacent vertices have a unique common neighbour. This gives us the constants (10, 3, 0, 1) where 10 is the number of vertices, 3 is the degree of each vertex, 0 is the number of common neighbours between any pair of adjacent vertices and 1 is the number of common neighbours between any pair of non-adjacent vertices. We have arrived at the definition of “strongly” regular graphs:

A graph G is called a strongly regular graph (srg) with parameters (v, k, \lambda, \mu) if it is k-regular with v vertices and satisfies the following: 

  • every pair of adjacent vertices have exactly \lambda common neighbours;
  • every pair of non-adjacent vertices have exactly \mu common neighbours. 

Therefore, the Petersen graph is an srg(10, 3, 0, 1). In fact, it is the only possible graph with those parameters. To make the idea more clear I would state that  a cycle of length 5 is an srg(5, 2, 0, 1) and that every complete graph on n vertices is an srg(n, n-1, n-2, 0). We would say that an srg is non-trivial if the parameter \mu is non zero, which makes the complete graph a trivial srg. For non-trivial srg’s we can easily show that the diameter must be 2.

Now a crucial question, why are these graphs important? Or more specifically, why do mathematicians care about these graphs? I’ll try to give some reasons why. To quote Peter Cameron [1],

Strongly regular graphs stand on the cusp between the random and the highly structured.

One of the examples he gives is that while there is (up to isomorphism) a unique srg(36, 10, 4, 2), the number of srg(36, 15, 6, 6) is 32548. Moreover, while many of the strongly regular graphs are highly symmetrical (the Petersen graph has an automorphism group of size 120) there are strong indications that almost all strongly regular graphs are asymmetrical (trivial automorphism groups) [2,3].

Regarding the highly symmetrical srg’s, many of them are related to important finite groups which makes them interesting objects for group theorists. For example, this strongly regular graph of 100 vertices has the sporadic simple Hall-Janko group of order 604800 as its automorphism group:

(image by  Claudio Rochhini)

It belongs to a chain of strongly regular graphs called the Suzuki tower which correspond nicely to certain finite simple groups. In fact the Suzuki group was originally constructed as an automorphism group of the top most graph in that tower. Moreover, the G_2(4) graph in that tower was used by Andriy V. Bondarenko last year to find the smallest counter example to the Borsuk’s conjecture in geometry [4]. Borsuk asked this question in 1933,

Can every bounded subset E of the space \mathbb{R}^n be partitioned into (n+1) sets, each of which has a smaller diameter than E?

It was proved that the answer is yes for several small cases and also in general if you assume some extra conditions. But in 1993 it was shown by Kalai and Kahn that the general answer to this problem is no. They found a counter example in dimension 1325 and for every dimension greater than 2014. The example that Bondarenko constructed was in dimension 65.

There are strongly regular graphs corresponding to latin squaresgeneralized quadranglesassociation schemesHadamard matrices, designs, sporadic groups, root systems and several other combinatorial/algebraic structures in mathematics. They pop up in the strangest of places from quantum physics [5], to computational complexity theory [6], to theoretical chemistry [7]. And I believe that they are highly interesting mathematical objects in their own right.

For more on these graphs, you can refer to [1] or this book by Brouwer and Haemers. These graphs were originally introduced by R.C. Bose in this paper from 1963. An interesting blog post on triangle free strongly regular graphs by Peter Cameron can be found here.

[1] Strongly Regular Graphs by Cameron (and some more notes from his course at St Andrews on Advanced Combinatorics)
[2] Are almost all srg’s rigid? (mathoverflow)
[3] Examples of rigid srg’s (mathoverflow)
[4] On Borsuk’s conjecture for two-distance sets
[
5] Global Symmetry is Unnecessary for Fast Quantum Search
[
6] On the Automorphism Groups of Strongly Regular Graphs
[7] Energy of graphs
[8] Strongly Regular Graphs by Brouwer

Advertisements

About Anurag Bishnoi

Currently a maths PhD student at Ghent University working in the Incidence Geometry research group. I am broadly interested in combinatorics, finite geometry and group theory.
This entry was posted in Combinatorics and tagged . Bookmark the permalink.

3 Responses to Strongly regular graphs

  1. Pingback: Point-Line Geometries | Anurag's Math Blog

  2. Pingback: Count Twice! | Anurag's Math Blog

  3. Some basic properties of strongly regular graphs that one can take as exercises:

    1. Let \Gamma be a strongly regular graph with parameters (v, k, \lambda, \mu), then its complement \overline{\Gamma} is a strongly regular graph with parameters (v, v - k - 1, v - 2k + \mu - 2, v - 2k + \lambda).

    2. Let \Gamma be a strongly regular graph with parameters (v, k, \lambda, \mu), then \mu \leq k, with equality if and only if \Gamma is a complete multipartite graph.

    3. Let \Gamma be a strongly regular graph with parameters (v, k, \lambda, \mu), then \lambda + 1 \leq k, and the following are equivalent: (i) \Gamma is a disjoint union of complete graphs; (ii) k = \lambda + 1; (iii) \mu = 0; (iv) \Gamma is disconnected.

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