19
$\begingroup$

I have heard through the academic rumor mill (my advisor heard from so-and-so about a result they heard from big-name who saw it in some journal, etc.) of the following theorem:

Theorem: Almost all strongly regular graphs have trivial automorphism group.

This contrasts that most known families of strongly regular graphs have high symmetry, due to their constructions using algebraic objects.

Does anyone know the reference for this theorem? Also, what is the measure used to describe "almost all"?

$\endgroup$
4
  • $\begingroup$ Does the following transform preserve strong regularity? If so, I can believe the result. A method from looking at traveling salesman paths ( find a pair of disjoint edges and toggle, as in || switches to = ) is something that is likely to transform a graph with large automorphism group into one with much smaller automorphism group. Mindful iteration of this should produce many non-isomorphic rigid regular graphs from a given graph. Gerhard "Ask Me About System Design" Paseman, 2010.10.05 $\endgroup$ Oct 5, 2010 at 20:25
  • 1
    $\begingroup$ Strong regularity requires conditions on the number of common neighbors each pair of vertices have (one number of the pair form an edge, another number if the pair are not adjacent). This switching operation does not preserve this property. In fact, there are many sets of parameters for strongly regular graphs where there exists a unique unlabeled graph that fits those properties, but have large automorphism groups. $\endgroup$ Oct 5, 2010 at 21:06
  • $\begingroup$ hard to believe the strong regularity is very strong condition, and as I know all known examples are very specific, not probabilistic (and those specific examples have many automorphisms) $\endgroup$ Oct 5, 2010 at 21:47
  • 1
    $\begingroup$ @fedor At least it is a useful claim because most people would feel the same way as you: a srg is a delicate jewel with lots of symmetry. Actually that mainly applies to the ones that we can understand. $\endgroup$ Oct 6, 2010 at 18:28

3 Answers 3

11
$\begingroup$

The article Random strongly regular graphs? by Peter Cameron http://www.maths.qmul.ac.uk/~pjc/preprints/randsrg.pdf provides some information about what is known and why someone might make that claim.

First an example: There are 11,084,874,829 strongly regular graphs with parameters SRG(57,24,11,9) which arise from a Steiner triple system with 19 points (and 57 blocks); Of these 11,084,710,071 are rigid. (There might be other SRG(57,24,11,9)) MR2059752 (2005b:05035) Kaski, P; Östergård, P The Steiner triple systems of order 19. Math. Comp. 73 (2004), no. 248, 2075--2092 http://www.ams.org/journals/mcom/2004-73-248/S0025-5718-04-01626-6/S0025-5718-04-01626-6.pdf

Cameron explains that the SRG with smallest eigenvalue -m are of 4 types:

1) a complete multipartite graph with km blocks of size m (so $v=km$)

2) Produced from $m-2$ mutually orthogonal $k\times k$ Latin squares (so $v=k^2$, nodes connected if they are in the same row or column, or have the same symbol in one of the squares)

3) The vertices are the blocks of a Steiner system with blocks of size m (so $v={\binom{k}{2}}/{\binom{m}{2}}$.

4) A finite list of exceptions $\mathcal{L}(m)$.

Type 1 has a huge automorphism group, but there are not very many of them.
Type 2: For $m=3$, there are on order of $n^{n^2/6}$ latin squares of order $n$, most with trivial automorphism group.
Type 3: For $m=3$ one has Steiner triple systems as above, there are on order $n^{n^2}$ and most are rigid.

Much less is known about sets of $m$ mutually orthogonal latin squares and about Steiner systems with block size $m$.

There are also graphs whose lower two eigenvalues are irrational conjugates (in some ring).

Any graph with $n$ vertices is an induced subgraph of a SRG with at most $4n^2$ vertices. On the other hand, every finite group is the automorphism group of a SRG (if I recall correctly). So the feeling is that there are lots of SRG with lots of freedom to construct them and most are rigid.

The notion of switching is useful. In a STS a Pasch configuration is a set of 6 points and 4 triples abc ade fbe fcd. This would correspond to a 4-clique in the corresponding graph. Switching these to abe acd fbc fde would still leave a 4 clique in the graph but would shift around the connections to the rest of the graph. There can be more elaborate switches too (I think). With enough room one can probably destroy all automorphisms this way. Of the rigid STS(19) above, 2538 don't have any Pasch configurations but over 1,000,000,000 have 14 (similarly for 15 and 16).

$\endgroup$
2
$\begingroup$

This answer addresses only the last part of the question, about the "almost all".

In discrete settings, "almost all" often is not with respect to a measure: after all, a measure on a countable set is necessarily discrete, i.e., specified by assigning to each point a non-negative real number. Thus "almost all" simply means at all points in the support of the measure, which depending on the measure, could be any subset whatsoever. So the measure isn't really doing anything helpful here.

I don't know the specific result you have in mind, but I am willing to bet that "almost all" has the following meaning: for a positive integer $n$, let $\operatorname{RSR}(n)$ be the finite set of isomorphism classes of (loopless, without multiple edges) rigid* strongly regular graphs on $n$ vertices, and let $\operatorname{SR}(n)$ be the finite set of isomorphism classes of (loopless...) strongly regular graphs on $n$ vertices. Then

$\lim_{n \rightarrow \infty} \frac{\operatorname{RSR}(n)}{\operatorname{SR}(n)} = 1$.

*: i.e., with trivial automorphism group.

$\endgroup$
2
  • 2
    $\begingroup$ Your limit should be a one instead of a zero. Let me also add that the result may in fact be over a given range of parameters of the in the definition of strongly regular graphs. The analogue for regular graphs would be: for each fixed $d$, almost all $d$-regular graphs contain a Hamilton cycle. In other words, when studying regular graphs, "almost all" statements often are proved after having fixed the parameter(s) rather than over all possible parameters. $\endgroup$ Oct 5, 2010 at 22:05
  • $\begingroup$ @LAB: Thanks for catching the slip. As far as what the actual result is: sure, I have no idea. For what it's worth, I did MathSciNet searches: ("automorphism group" AND "strongly regular graph") and ("rigid" AND "strongly regular graph") and everything I got had lots of additional numerical parameters, as you say. $\endgroup$ Oct 6, 2010 at 2:51
1
$\begingroup$

Not an answer, but too long for a comment.

Given that strongly regular graphs have only three eigenvalues (one of which gives rise to a trivial one-dimensional eigenspace), my preferred hammer for this kind of problem is the "spectral" geometric realization, for which each automorphism induces a linear isometry.

With adjacency matrix, $A$, and eigenvalues $k$ (the common degree of each vertex), $r$, $s$, the spectral realizations of the graph have the following coordinate matrices (in which each column is the coordinate vector of a vertex):

$K := \frac{(A - r I)(A - s I)}{(k - r)(k - s)} \hspace{0.25in} R := \frac{(A - k I)(A - s I)}{(r-k)(r-s)} \hspace{0.25in} S := \frac{(A - k I)(A - r I)}{(s - k)(s - r)}$

These realizations are embedded in $n$-dimensional space, where $n$ is the number of vertices. The isometry property follows from the fact that, if $P$ is the permutation matrix (applied to $A$) corresponding to an automorphism, then it is also the linear transformation matrix applied to a spectral realization corresponding to an isometry. (That's one of the nice things about embedding in $n$-dimensional space.)

Note that $K$, $R$, and $S$ are eigen-matrices of $A$. Interpreting right-multiplication by $A$ geometrically, this says that the (vector) sum of the neighbors of a vertex $v$ is $\lambda v$, where $\lambda$ is the associated eigenvalue.

Vertex-regularity alone implies that $K$ is a multiple of the "all $1$s" matrix, $J$. (Strong regularity gives us specifically that $K = \frac{k+rs}{(k-r)(k-s)}J$.) This realization collapses all vertices to a single point, so the automorphism-induced isometries aren't terribly interesting. Unlike with most vertex-regular graphs, though, we only have two other cases to consider.

Is there anything obvious about the geometry of the $R$ and $S$ realizations in "almost all" cases that makes them asymmetric? I don't know. I got as far as computing these matrices for the (two non-trivial) 1-automorphism strongly-regular graphs provided by Mathematica's "GraphData[]" function, but nothing jumped out at me as being different from the highly-symmetric cases. I haven't investigated how the relations among the parameters of strongly-regular (or merely distance-regular) graphs might come into play.

Checking for a trivial isometry group for $R$ and $S$ probably turns out to be exactly as difficult as checking for a trivial automorphism group for $A$. (It'd be a piece of cake if, say, all vertices happened to be at different distances from the origin.) Nevertheless, I like having a geometric model handy ... even if it lives in too many dimensions for me to actually see.

$\endgroup$
1
  • $\begingroup$ One extra fact for distance-regular graphs: Writing $A_d$ for the "distance-$d$ adjacency matrix", powers of $A$ can be written as linear combinations of the $A_d$. (Note that $A_0 = I$ and $A_1 = A$.) Consequently, if $M$ is one of $K$, $R$, and $S$, then $M = m_0 I + m_1 A + m_2 A_2$. (Computing the $m$s is an exercise for the reader.) This says that the $(i,j)$-th entry of $M$ is $m_d$, where $d$ is the (combinatorial) distance from vertex $i$ to vertex $j$. This may not help the analysis, but it demonstrates structure in $K$, $R$, $S$ that might not be apparent from the definitions above. $\endgroup$
    – Blue
    Oct 6, 2010 at 7:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.