Let $A = \big[{1\ 1\atop 1\ 0}\big]$, and let $G_n$ be the graph whose adjacency matrix is $A^{\otimes n}$. Also let $\kappa(G)$ denote the number of spanning trees of $G$. From a significant amount of computational evidence, it seems highly likely that that $\kappa(G_n) \mid \kappa(G_{n+1})$ always holds $n \geq 0$. In fact it seems that $\kappa(G_n)^2 \mid \kappa(G_{n+1})$. I have tried attacking this problem by analyzing the Laplacian of the graph, but this seems difficult because the Laplacian does not behave nicely under tensor product. I have been working on this for a while so I would appreciate any suggestions on how one might tackle this.

  • $\begingroup$ In the $n=1$ case -- what does it mean that one of your diagonal entries is $1$, one $0$? Does one have a self-loop the other doesn't? $\endgroup$ – Allen Knutson Apr 5 '13 at 3:30
  • $\begingroup$ Yes, I give one of the vertices a self-loop, so that the matrix for $G_n$ can be written nicely. It has no bearing on spanning trees of course. (Also the graph in question is formed by taking all subsets of an n-element set as vertices, and connecting disjoint subsets with edges. The loop corresponds to the empty set being disjoint from itself.) $\endgroup$ – user32835 Apr 5 '13 at 3:57
  • $\begingroup$ I think you should try the Q-spectrum. See Thm 2.3 (4), Thm 2.18 and bottom of page 75, Lem 2.20 of "Counting Spanning Trees", citeseerx.ist.psu.edu/viewdoc/summary?doi= $\endgroup$ – Martin Rubey Apr 5 '13 at 7:04

The answer is actually as nice as could be. The number of spanning trees of $G_n$ is

$$ \frac{1}{3^n}2^{n 2^{n-1}}\prod_{k=0}^{n-1} \big(1-(-2)^{k-n}\big)^{\binom{n}{k}} $$

This follows directly from the theorems in the comment above. The divisibility (what a beautiful word!) properties then follow from the formula.

  • $\begingroup$ +1 This was gonna be exactly my answer, but you beat me to it! (Just mentioning for the interested that Runge showed in his Ph.D thesis a version of the Matrix Tree Theorem that holds for the Q-Laplacian, and somehow it is not that well known (though trivial to prove) that this Laplacian is a friend of tensor products....) $\endgroup$ – Suvrit Apr 5 '13 at 17:22

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.