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$
$\endgroup$
3
-
$\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 KnutsonCommented Apr 5, 2013 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$– user32835Commented Apr 5, 2013 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=10.1.1.36.9128 $\endgroup$– Martin RubeyCommented Apr 5, 2013 at 7:04
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
answered Apr 5, 2013 at 10:18
-
$\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$– SuvritCommented Apr 5, 2013 at 17:22