23
$\begingroup$

Let $G$ be a regular graph of valence $d$ with finitely many vertices, let $A_G$ be its adjacency matrix, and let $$P_G(X)=\det(X-A_G)\in\mathbb{Z}[X]$$ be the adjacency polynomial of $G$, i.e., the characteristic polynomial of $A_G$. In some graphs that came up in my work, the adjacency polynomials $P_G(X)$ have a lot of factors in $\mathbb Z[X]$, many of them repeated factors. So my questions are:

  1. Is it common for the adjacency polynomial of a regular graph to be highly factorizable in $\mathbb Z[X]$, and to have many repeated factors?

  2. If not, what are the graph-theoretic consequences of having many small-degree factors?

  3. If not, what are the graph-theoretic consequences of having factors appearing to power greater than 1?

To give an idea of the numbers involved, one example was a connected 3-regular graph with 64 vertices, and $$ P_G(X) = (x - 3)x^{3}(x + 1)^{3}(x^2 - 3 x + 1)^{3}(x^2 - x - 3)^{3}(x^2 - x - 1)^{6} (x^2 + x - 3)^{3}(x^3 - 3 x^2 - x + 4)^{2}(x^3 - 4 x + 1) (x^6 - x^5 - 11 x^4 + 9 x^3 + 31 x^2 - 19 x - 8)^{3} $$

I've looked at a couple of references and tried a Google search, but didn't find anything relevant.

$\endgroup$
5
  • 12
    $\begingroup$ Do your graphs have a lot of automorphisms? This will induce a factorization of $P_G(X)$. $\endgroup$ Sep 6 '20 at 2:33
  • 2
    $\begingroup$ Large eigenspaces of the adjacency matrix often point to either large symmetry, or more generally, to large regularity of the graph (whatever that means precisely). You could check whether your graph is distance-regular or at least $k$-walk-regular for some small $k\ge1$ as this often comes with large eigenspaces. $\endgroup$
    – M. Winter
    Sep 6 '20 at 9:05
  • 3
    $\begingroup$ Since the graphs seems to have many eigenspaces of dimension three, I would probably try to get some intiution for its structure by plotting the 3-dimensional spectral graph realizations to these eigenvalues. Maybe some of these are of a quite recognizable shape (a Platonic solid etc). See here for what I mean by "spectral realization". $\endgroup$
    – M. Winter
    Sep 6 '20 at 11:32
  • 2
    $\begingroup$ Let me add that there seem to be quite a few examples of graphs for which $P_G(X)$ factors more than is explained by symmetry. An example is mathoverflow.net/questions/369515. For a different kind of example of this phenomenon of "extra factorization," see Exercise 10.9(d) of my book Algebraic Combinatorics, second ed. $\endgroup$ Sep 6 '20 at 14:49
  • 1
    $\begingroup$ @RichardStanley Thanks. I think that my graph does have a large automophism group. I'm not sure I can compute it exactly, but pulling out a large piece should give something. It's also helpful to know that although symmetry causes factorization, the converse isn't necessarily true; I'll keep that in mind. $\endgroup$ Sep 6 '20 at 22:50
26
$\begingroup$

Expanding on Richard's comment: let me rename your graph to $S$ and consider the adjacency matrix $A$ abstractly as a linear operator acting on the free vector space $\mathbb{C}[S]$ on (the vertices of) $S$, and let $G$ be its automorphism group (this is why I wanted a new name). Then $\mathbb{C}[S]$ is a completely reducible representation of $G$ and $A$ is an endomorphism of this representation. Hence if we write

$$\mathbb{C}[S] \cong \bigoplus_i n_i V_i$$

where $V_i$ are the irreducibles, then $A$ is an element of the endomorphism algebra

$$\text{End}_G(\mathbb{C}[S]) \cong \prod_i M_{n_i}(\mathbb{C}).$$

This means more explicitly that $A$ is conjugate over $\mathbb{C}$ to a block diagonal matrix with a block for each isotypic component (hence its characteristic polynomial factors accordingly). In the nicest possible case the decomposition above is multiplicity-free in which case the endomorphism algebra is a product of copies of $\mathbb{C}$ and we just have that $A$ must act by a scalar $\lambda_i$ on each $V_i$ that occurs in the decomposition, which contributes a multiplicity of $\dim V_i$ to $\lambda_i$ as a root of the characteristic polynomial and hence, over $\mathbb{Q}$, contributes a multiplicity of $\dim V_i$ to the minimal polynomial of $\lambda_i$ as a factor of the characteristic polynomial.

(I think the result of this analysis comes out the same if you work over $\mathbb{Q}$ from the beginning but it's more annoying to describe.)

I work through a few examples of this in my old blog post The Schrodinger equation on a finite graph, where I was trying to understand via a toy model the quantum mechanical phenomenon of group symmetries introducing "degeneracies," which is physics speak for eigenvalues (of the Hamiltonian in this case) of multiplicity greater than $1$.

The "most degenerate" case is the complete graph $S = K_n$, where $G = S_n$ and the corresponding representation is a copy of the trivial representation and an irreducible representation of degree $n-1$. This means the adjacency matrix $A$ must have at most two eigenvalues, one with multiplicity $1$ and one with multiplicity $n-1$, which turn out to be $n-1$ and $-1$ respectively (this is easily computed by computing $\text{tr}(A)$ and $\text{tr}(A^2)$, or just finding all the eigenvectors of $A + I$), inducing a factorization

$$\det (tI - A) = (t - n + 1)(t + 1)^{n-1}$$

with a factor of multiplicity $n-1$.

One of the "least degenerate" cases where the automorphism group still acts transitively on vertices is $S = C_n$ the cycle graph, where $G = D_n$ is the dihedral group and the corresponding representation splits up into mostly $2$-dimensional irreps. This reflects the fairly mild degeneracies of the eigenvalues of the adjacency matrix, which are $2 \cos \frac{2\pi k}{n}, k = 0, \dots n-1$, and/but which also organize themselves into nontrivial Galois orbits coming from the action of the Galois group of $\mathbb{Q}(\zeta_n)$.

$\endgroup$
2
  • 1
    $\begingroup$ Marvelous. Particularly your blog post: I wonder if there is some literature on taking your "toy model" seriously. By this I mean: can one approximate at any level of accuracy any quantum system as a graph quantum model when the finite graph grows? I bet it can. On a related note: Feynman ' s approach via paths actually becomes quantum random walks on your graph, and no infinities involved... $\endgroup$ Sep 6 '20 at 20:21
  • 2
    $\begingroup$ Thanks. This is all very helpful, especially the use of the symmetry group of the graph, and the representation that you describe, to deduce factorization. For my graphs, I expect that the symmetry group is fairly large, but not necessarily easy to compute, so I may be able to play the factorization off against potential pieces of the symmetry group. In any case, you've provided me much food for thought. $\endgroup$ Sep 6 '20 at 22:54
8
$\begingroup$

In a comment I said that large eigenspaces of the adjacency matrix may point to large symmetry or regularity in the graph. For example, let me explain why highly symmetric graphs have large eigenspaces (that is, large factors in their characteristic polynomial).

A symmetry $\sigma\in\def\Aut{\mathrm{Aut}}\Aut(G)$ is a permutation of the vertex set $V=\{1,...,n\}$. Let $P_\sigma\in\def\RR{\Bbb R}\RR^{n\times n}$ be the associated permutation matrix. The symmetries of a graph can be characterized using its adjacency matrix as follows: a permutation $\sigma\in\mathrm{Sym}(V)$ satisfies

$$\sigma\in\Aut(G)\quad\Longleftrightarrow\quad AP_\sigma=P_\sigma A.$$

But this means, for any eigenvalue $\theta\in\mathrm{Spec}(A)$, if $u\in\RR^n$ is a $\theta$-eigenvector, then so is $P_\sigma u\in\RR^n$ for all the $\sigma\in\Aut(G)$:

$$A(P_\sigma u)=(AP_\sigma) u = (P_\sigma A)u = P_\sigma (Au)=P_\sigma(\theta u)=\theta(P_\sigma u)$$

So the $\theta$-eigenspace contains $\mathrm{span}\{P_\sigma u\mid \sigma\in\Aut(G)\}$ which can be quite large, depending on $\Aut(G)$.

Another way to say this: the eigenspaces of $A$ are invariant subspaces w.r.t. $\Aut(G)$, and if $\Aut(G)$ has no small (irreducible) invariant subspaces then $A$ cannot have small eigenspaces.


On the other hand, generic regular graphs do probably not have integer eigenvalues. So there is no reason for any such adjacency polynomial to factor over $\Bbb Z$ into many small factors (ignoring the trivial factor). So I would say this points to some structure in your graph, but it is hard to say what it is whitout knowing more about the graph.

$\endgroup$
1
  • $\begingroup$ Thanks. I actually have a large infinite group that acts on my graph, although it is not clear (to me, at least) what the quotient of that action is, nor whether the image will be the entire automorphism group (although I suspect that it generally will be). It's also good to know, as Richard Stanley also pointed out in the comments, that although large automorphism group (often) leads to factorization of the adjacency polynomial, the converse need not hold. $\endgroup$ Sep 6 '20 at 22:57
4
$\begingroup$

Consider the category $Gph$ whose objects are directed graphs. That is the topos defined on the small category $C$ which has two objects $0,1$ and two morphisms $s,t:0\rightarrow 1$. A directed graph is thus defined by by a contravariant functor $D:C\rightarrow Set$ where we call $D(0)$ the set of nodes and $D(1)$ the set of arrows, $D(s)$ is the source map and $D(t)$ is the target map. An example of graphs is the $n$-cycle directed graph.

I have constructed with Bisson a Quillen model on the category $Gph$ such that a morphism $f:X\rightarrow Y$ is a weak equivalene if and only if for every $n>0$ the induced map $Hom(C_n,X)\rightarrow Hom(C_n,Y)$ is bijective.

Let $X$ is and $Y$ be finite graphs, we say that they are almost isospectral if the characteristic polynomial of their adjecency matrices have the same non zero eigenvalues.

The following conditions are equivalent:

  1. Two finite directed graphs for the Quillen model above are weakly equivalent.

  2. Two finite directed graphs have the same Zeta serie.

  3. Two finite directed graphs are almost isospectral.

The third condition implies that two finite graphs are weakly equivalent for the Quillen model if the factors of their characteristic polynomial distinct of $X^p$ are equal.

We have also computed the homotopy category of this closed model and showed that it is equivalent to the category of periodic $\mathbb{Z}$-sets.

This shows that a finite graph is equivalent to finite set of cycles and enables to relate the degree of the factors of the characteristic polynomial of the finite graph $X$ to its image in the homotopy category which is a set of cycles.

For example, for this model, acyclic object are trees, and the characteristic polynomial of a tree is of the form $X^n$. In fact in this model if $X^p$ is a non trivial factor of the characteristic polynomial of the graph $G$, there is a weak cofibration $c:G'\rightarrow G$ (a whiskering) which is defined by attaching trees to $G'$.

https://arxiv.org/pdf/0802.3859.pdf

https://arxiv.org/pdf/0906.4087.pdf

$\endgroup$
4
$\begingroup$

Corollary 2.7 of Norman Biggs's book Algebraic Graph Theory says that if $d$ is the diameter of the graph, then it has at least $d+1$ distinct eigenvalues. (This bound is tight, and is achieved for example by distance-regular graphs.) So in particular, having a lot of repeated eigenvalues does not necessarily indicate a lot of automorphisms; it might just mean that the diameter is small. For example, a strongly regular graph has only three distinct eigenvalues but often has trivial automorphism group.

$\endgroup$
1
  • $\begingroup$ Thanks. I'll keep that in mind. Although I think that my graphs do, in fact, have a large automorphism group. But this will prevent me from drawing too much of a conclusion from the factorization! $\endgroup$ Sep 6 '20 at 22:59
2
$\begingroup$

An observation about graph isomorphism (GI) since you ask about powers greater than 1.

GI is polynomial time solvable for graphs with bounded eigenvalues multiplicity (the largest exponent in the factorization of your polynomial).

I suspect random graphs to have bounded multiplicities and random non-isomorphic graphs to have different polynomials.

A very extreme examples are Paley graphs:

sage: g1=graphs.PaleyGraph(37);factor(g1.characteristic_polynomial())
(x - 18) * (x^2 + x - 9)^18
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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