11
$\begingroup$

Given a (simple) graph $G=(V,E)$ with $V=\{1,...,n\}$ and let $A$ be its adjacency matrix.

I am interested in the representation theory (over $\Bbb R$) of the automorphism group $\def\Aut{\mathrm{Aut}}\Aut(G)$. One way to generate such representations is via spectral graph theory. If $\lambda$ is an eigenvalue of $A$ and $\{e_1,...,e_m\}$ is an orthonormal basis of the associated eigenspace $\def\Eig{\mathrm{Eig}}\Eig_\lambda(G)$, then the rows of the matrix

$$U:=\begin{pmatrix} | & & |\\ e_1 & \cdots & e_m \\ | & & | \end{pmatrix}$$

can be interpreted as the positions $v_i\in\Bbb R^m,i=1,...,n$ of the vertices of $G$ in a graph embedding. What is special about this embedding is, that it realizes all the symmetries of $G$. This means, for each automorphism $\phi\in\Aut(G)$, there is a linear map $M_\phi\in\mathrm{GL}(m,\Bbb R)$ with $v_{\phi(i)}=M_\phi v_i$. This gives a real representation $\Aut(G)\to\mathrm{GL}(m,\Bbb R),\phi\mapsto M_\phi$.

My questions are:

Was this construction of real representations of $\Aut(G)$ already studied somewhere in the literature?

and especially:

When are these respresentations (real) irreducible?

This answer mentions graphs with trivial symmetry group but large eigenspaces, which therefore cannot provide irreducible representations. However, I am interested in graphs with a lot of symmetries, especially arc-transitive graphs. In all the cases I studied, all the representations turned out to be irreducible.

Update

  • A similar question was asked on Math.StackExchange and received an interesting answer from C. Godsil. Especially the last parenthesized sentence leaves space for an interesting counter-example.

  • The searchable terminology seems to be "reducible/irreducible eigenspaces of graphs". At least this lead me to the following paper

    G. Berkolaiko, W. Liu: Eigenspaces of Symmetric Graphs are not Typically Irreducible (2018)

    However, I am not aware of a direct connection to the problem stated here, partially because the paper's terminology is not very familiar to me, yet.

Improve this question
$\endgroup$
6
  • $\begingroup$ not all $\lambda$'s lead to a meaningful embedding. E.g. if the graph is regular then the maximal eigenvalue has multiplicity 1... $\endgroup$
    – Dima Pasechnik
    Commented Nov 17, 2018 at 13:35
  • $\begingroup$ @DimaPasechnik I admit: "embedding" is usually used for injective maps. Here I mean just any mapping $V\to\Bbb R^d$, injective or not. The non-injective ones then correspond to non-faithful representations. The largest eigenvalue (in a connected regular graph) will always give the trivial representation $\phi\to\mathrm{id}$ (and thats totally meaningful). $\endgroup$
    – M. Winter
    Commented Nov 17, 2018 at 14:02
  • $\begingroup$ How does such a trivial representation "realise all the symmetries of $G$" ? $\endgroup$
    – Dima Pasechnik
    Commented Nov 17, 2018 at 21:15
  • $\begingroup$ @DimaPasechnik In the sense as explained in the post: for every automorphism $\phi\in\mathrm{Aut}(G)$ there is an orthogonal map $M_\phi\in\mathrm{GL}(m,\Bbb R)$ with $M_\phi v_i=v_{\phi(i)}$. Of course, the injective realizations are the more interesting ones, but the others fit the definition and might carry interesting information about the graph. It's also less relevant for the question, as a source which only discussed the faithful ones would be interesting too. $\endgroup$
    – M. Winter
    Commented Nov 17, 2018 at 22:49
  • $\begingroup$ OK, but "realises all the symmetries of G" reads like plain English for "provides a faithful representation of Aut(G)", isn't it? $\endgroup$
    – Dima Pasechnik
    Commented Nov 18, 2018 at 0:42

1 Answer 1

Reset to default
2
$\begingroup$

Recently I found an arc-transitive graph (and then many more) for which some eigenspaces are reducible, something that I believed might not occure.

The example is the Shrikhande graph, a strongly regular graph with parameters $(16,6,2,2)$.

The spectrum consists of eigenvalues $6^1, -2^6, 2^9$ (multiplicities in the exponent), where only the eigenspace of $2$ is reducible. I cannot tell you how exactly the eigenspace decomposes since my knowledge about this stems from computing the characters and the Frobenius-Schur indicator as explained here.

There are other examples: e.g. $C_{10}\times C_{10}$ and some circulant graphs that have one suspiciously large eigenspace that decomposes. I have not investigated for what parameters these reducible eigenspaces occure, I just know that they are not always present.

What is interesting though, is, that the eigenspace to the second largest eigenvalue seems to be always irreducible. This is interesting since this eigenspace is related to the algebraic connectivity and is a central object of my research. I will have to investigate whether this is always true.

Update

Even the eigenspace of the second-largest eigenvalue does not have to be irreducible. I found some examples by computing Frobenius-Schur indicators for various arc-transitive graphs. However, counter-examples seem to be rare.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .