Maximal class of simple graphs of order $n$ with mutually distinct numbers of spanning trees - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T05:24:07Z http://mathoverflow.net/feeds/question/100816 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/100816/maximal-class-of-simple-graphs-of-order-n-with-mutually-distinct-numbers-of-spa Maximal class of simple graphs of order $n$ with mutually distinct numbers of spanning trees Jernej 2012-06-27T22:26:53Z 2012-07-06T09:37:06Z <p>This problem in some ways related to <a href="http://mathoverflow.net/questions/93656/minimal-graphs-with-a-prescribed-number-of-spanning-trees" rel="nofollow">this</a> post.</p> <blockquote> <p>Let $A_n$ be the set of all integers $x$ such that there exist a connected simple graph of order $n$ having precisely $x$ spanning trees. Study the growth rate of $|A_n|.$ </p> </blockquote> <p>The question was raised by J.Sedlacek in his paper entitled: <em>On the number of spanning trees of finite graphs, Cas. Pro. Pest Mat., Vol. 94 (1969) 217-221.</em> </p> <p>Sedlacek was able to show that $|A_n| = \omega(n)$ and remarked that it is not known if $|A_n| = \omega(n^2).$</p> <p>Following are some observations about $|A_n|.$</p> <ol> <li><p>Clearly $|A_n| \leq n^{n-2}$ and $|A_n| \leq |A_{n+1}|$</p> <ul> <li>Playing with prime partitions a bit it is possible to show that</li> </ul> <p>$$|A_n| = \omega(\sqrt{n}e^{\frac{2\pi}{\sqrt{3}}\sqrt{n/\log{n}}})$$</p> <ul> <li>The following table can be computed using sage+nauty:</li> </ul></li> </ol> <p>$$\begin{array}{ccc} n &amp; |A_n| &amp; \frac{n^{n-2}}{|A_n|}\\ 1 &amp; 1 &amp; 1 \\ 2 &amp; 1 &amp; 1 \\ 3 &amp; 2 &amp; 1.5 \\ 4 &amp; 5 &amp; 3.2 \\ 5 &amp; 16 &amp; 7.8 \\ 6 &amp; 65 &amp; 19.9\\ 7 &amp; 386 &amp; 43.5\\ 8 &amp; 3700 &amp; 70.8 \\ 9 &amp; 55784 &amp; 85.7\\ 10 &amp; 1134526 &amp; 88.1 \\ 11 &amp; 27053464 &amp; 87.1 \\ \end{array}$$</p> <p>The bound mentioned under 2. was obtained using a construction of graphs with cut vertices. Since almost all graphs are blocks it is (in a way) reasonable to ask</p> <blockquote> <p><strong>Question.</strong> Is there a construction (using blocks) that can improve bound 2.?</p> </blockquote> <p>I believe that this should also be provable:</p> <blockquote> <p><strong>Conjecture.</strong> $|A_n| = \omega(k^n)$ for all $k \in \mathbb{N}.$</p> </blockquote> <p>In case this turns out to be a hard problem I would at least like to extend table 3. further. I am currently computing $|A_n|$ by generating all connected graphs of order $n$ with at least $n$ edges, computing their spanning trees and count distinct such numbers. One optimization could be derived by using the fact that $A_n \subset A_{n+1}$ but this is just a minor thing. I therefore leave the following question for the end:</p> <blockquote> <p><strong>Question.</strong> How can we compute $|A_n|$ quickly?</p> </blockquote> http://mathoverflow.net/questions/100816/maximal-class-of-simple-graphs-of-order-n-with-mutually-distinct-numbers-of-spa/100823#100823 Answer by Igor Pak for Maximal class of simple graphs of order $n$ with mutually distinct numbers of spanning trees Igor Pak 2012-06-28T00:02:52Z 2012-06-28T00:02:52Z <p>I don't have an answer to your asymptotics question, but I do have an idea how to approach your problem. Consider a graph $\Gamma=\Gamma(G_1,\ldots,G_k,H)$, where $H$ is a simple graph on $k$ vertices, where $\Gamma$ is obtained by making $G_i$ to be "parts" and connecting every vertex in $G_i$ with every vertex in $G_j$ if $(i,j)\in H$. This construction generalizes a multipartite graphs and hopefully should give you a better asymptotics if you set up the induction right. </p> <p>Define $F_G(z) = \sum_r f(G,r) z^r$, where $f(G,r)$ is the number of rooted spanning forests in $G$ with $r$ roots. This way $F_G(0)$ is $n$ times the number of spanning trees in $G$, and $F_G(1)$ is the number of spanning trees in $\widehat G$, defined as a vertex connected to all $v\in G$. Turns out, $F_\Gamma$ is a product of $F_{G_i}$ and $F_H$ with appropriate substitutions. See <a href="http://www.math.ucla.edu/~pak/papers/PP-trees-journal.pdf" rel="nofollow">this</a> really short note, and <a href="http://www.math.ucla.edu/~pak/papers/KPP-volume.ps" rel="nofollow">this preprint</a> which explains it better. </p>