Almost all trees are cospectral (Allen Schwenk's 1973 article)

522 Views Asked by At

I am currently working on the following article: https://www.researchgate.net/publication/245264768_Almost_all_trees_are_cospectral.

There are a few things that I don't understand, and since the article was released in 1973, it's a bit difficult for me to find help or any explanations.

Firstly, I don't really understand how Schwenk counts the matchings in the proof of Theorem 2 (on the characteristic polynomial of the coalition of two trees).

Secondly on page 23 he wrote that "Equations (10) and (11) are readily usable by a computer program to generate the first several coefficients of $r^{(n)}(x)$ . This has been done, and the first 39 coefficients of $r^{(n)}(x)$ have been computed for $2\leq n \leq 9$." Therefore I thought I could compute these coefficients with a python code, but I can't find out a way to do that. I've asked both my math and computer science teachers and they have no idea how to do it. The problem is that in equations (11) and (12), $S^{(n)}(x)$ is a function of a series of $S^{(n)}(x^k)$.

I also feel like he's jumping to conclusions in the proof of Theorem 7.

I'd be really grateful if anyone could explain that to me because I can't find anyone who has enough time / skills to do it. Thanks in advance!

1

There are 1 best solutions below

1
On BEST ANSWER

Results that imply Theorem 2 appear in most books that treat graph spectra - note that the formula holds for all graphs, not just trees. Second, to extract coefficients, you need tools for manipulating power series. Now Schwenk would have been programming in Fortran on a computer that was probably less powerful than your cell phone, but now packages such as sage/maple/mathematica... fortunately have this stuff built in. You can find an example of how to do the sort of calculations in sage at http://linear.ups.edu/eagts/eagts.html (chapter 8). (I realise that this not as complete an answer to your question as you might have hoped for, but such answer requires more time and space than are available.)