Minimal graphs with a prescribed number of spanning trees - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T16:58:49Z http://mathoverflow.net/feeds/question/93656 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/93656/minimal-graphs-with-a-prescribed-number-of-spanning-trees Minimal graphs with a prescribed number of spanning trees Jernej 2012-04-10T12:45:21Z 2013-02-18T21:15:09Z <p>As its long ago since Erd&#337;s died and mathoverflow is the second best alternative to him (for discussing personal problems), I'd like to start a fruitful discussion about the following problem that I find very interesting.</p> <blockquote> <p>Let $n \geq 3$ be an integer and let $\alpha(n)$ denote the least integer $k$ such that there exists a simple graph on $k$ vertices having precisely $n$ spanning trees. What is the asymptotic behaviour of $\alpha$ ?</p> </blockquote> <p><strong>Motivation.</strong> I was introduced to the question through this <a href="http://rjlipton.wordpress.com/2009/06/24/the-inverse-spanning-tree-problem/" rel="nofollow">post</a> on Dick Lipton's blog. As it turns out, the question was posed already in 1970 by the Czech graph theorist J. Sedlacek (On the minimal graph with a given number of spanning trees, Canad. Math. Bull. 13 (1970) 515–517)</p> <p><strong>What is known?</strong></p> <p>Sedlacek was able to show that for every (not so) large $n$</p> <p>$\alpha(n) \leq \frac{n+6}{3}$ if $n \equiv 0 \pmod{3}$ and $\alpha(n) \leq \frac{n+4}{3}$ if $n \equiv 2 \pmod{3}.$</p> <p>Following is a summary of what I was able to find out.</p> <p>Since the equation $n = ab+ac+bc$ is solvable for integers $1 \leq a &lt; b &lt; c$ for all but a finite number of integers $n$ (see <a href="http://mathoverflow.net/questions/6388/prime-numbers-p-not-of-the-form-ab-bc-ac-0-a-b-c-and-related-questi" rel="nofollow">this</a> post) it can be deduced (by considering the graph $\theta_{a,b,c}$ which has $ab+ac+bc$ spanning trees) that for large enough $n \not \equiv 2 \pmod{3}$ </p> <p>$$\alpha(n) \leq \frac{n+9}{4}.$$</p> <p>Moreover, the only fixed points of $\alpha$ are 3, 4, 5, 6, 7, 10, 13 and 22.</p> <p>By generalizing the approach and considering the graphs $\theta_{x_1,\ldots,x_k}$ one could try to lower the constant in the fraction of the inequality by an arbitrary amount. As it <a href="http://mathoverflow.net/questions/33411/a-generalisation-of-the-equation-n-ab-ac-bc" rel="nofollow">turns out</a> it is not know weather every large $n$ is then expressible as $n = x_1\cdots x_k(\frac{1}{x_1} + \cdots + \frac{1}{x_k})$ for suitable integers $1 \leq x_1 &lt; \cdots &lt; x_k.$</p> <p>Even if that method would work out, the bound would most probably still be suboptimal. According to the graph (created by randomly generating graphs and calculating the number of their spanning trees) it seems reasonable to conjecture that</p> <p><strong>Conjecture.</strong></p> <blockquote> <p>$$\alpha(n) = o(\log{n})$$</p> </blockquote> <p><img src="http://shrani.si/f/1G/lc/2yL7fZJd/graf.png" alt="alt text"></p> <p>The conjecture is clearly justifiable for highly composite numbers $n$ (consider the graph obtained after identifying a common vertex of the cycles $C_{x_1},\ldots,C_{x_k}$ for suitable odd factors $x_1, \ldots,x_k$ of $n$) but It fails for $n$'s that are primes.</p> <p>It is evident to me that I lack the tools necessary for attacking this conjecture so any kind of suggestions (where to look for a possible answer, what kind of tools should I learn..) related to it are very welcome!</p> <p>Edit. If anyone is willing to work on this problem, I'd be glad to collaborate since I'd benefit much from it! </p> http://mathoverflow.net/questions/93656/minimal-graphs-with-a-prescribed-number-of-spanning-trees/122093#122093 Answer by Günter Rote for Minimal graphs with a prescribed number of spanning trees Günter Rote 2013-02-17T19:46:25Z 2013-02-18T21:15:09Z <p>No answer, but a related question: The number $n$ of spanning trees in a graph with $k+1$ vertices is the determinant of a $k\times k$ matrix with integer entries between $-1$ and $k$.</p> <blockquote> <p>For given $n$, what is the smallest $k=\beta(n)$ such that $n$ is the determinant of such a matrix?</p> </blockquote> <p>Of course, $\alpha(n)\ge \beta(n)+1$. Variations of this problem might restrict to symmetric, or diagonally dominant matrices, or on the other hand allow entries between $-k$ and $k$.</p> <p>Are any bounds known about THIS question?</p> <p><strong>Additions</strong> (incorporating the remark by Will Sawin): For example, $$\left| \begin {matrix} 4&amp;7&amp;1&amp;3\cr -1&amp;10&amp;0&amp;0 \cr 0&amp;-1&amp;10&amp;0\cr 0&amp;0&amp;-1&amp;10 \end {matrix} \right| = 4713.$$ In this way, with $k$ as the base instead of 10, one gets all numbers up to $k^k$ (and a little more). The upper bound on the determinant from the Hadamard inequality is $k^{3k/2}$. With the lower bound $-1$ on the entries, this bound can probably be improved, since the row vectors of the matrix cannot be simultaneously "long" and close to orthogonal. </p> <p>One can work this determinant into the number of <em>directed</em> spanning trees of a <em>multigraph</em>: $$\left| \begin {matrix} 4&amp;-7&amp;-1&amp;-3\cr -1&amp;10&amp;0&amp;0 \cr 0&amp;-1&amp;10&amp;0\cr 0&amp;0&amp;-1&amp;10 \end {matrix} \right| = 4000-713=3287.$$ Let us add a fifth column to make column sums zero: $$\begin {pmatrix} 4&amp;-7&amp;-1&amp;-3\cr -1&amp;10&amp;0&amp;0 \cr 0&amp;-1&amp;10&amp;0\cr 0&amp;0&amp;-1&amp;10\cr -3&amp; -2&amp;-8&amp;-7 \end {pmatrix}$$ The digits of the determinant are now in the last row. This number 3287 is equal to the number of oriented spanning trees (arborescences) on a directed multigraph $G$ on 5 vertices which are oriented away from the root node 5. The graph $G$ is obtained by taking the negative off-diagonal entries as edge multiplicities. (The arcs going into node 5, which would be the fifth column, are obviously irrelevant.) One can also figure out directly that this is the number of arborescences, by classifying them into those 3000 that use the arc $(5,1)$ and the remaining 287 that don't.</p> <p>For directed graphs, one can get rid of multiple edges by subdividing them. The new intermediate vertex on an edge must have exactly one incoming arc in every tree, and since the indegree is 1 this arc is fixed, and the number of spanning arborescences is as in the original graph. Moreover, all multiple edges go out either from vertex 1 or from vertex $k+1=5$. Multiple edges emanating from one vertex and going to different vertex can share the intermediate subdivision vertex. Thus, we need in total only $2(k-2)$ extra vertices to eliminate multiple arcs, $k-2$ from vertex 1 and $k-2$ from vertex $k+1$, for a total of $3k-3$. (I did not work out how this argument looks when translated into matrix terms.)</p> <blockquote> <p>Every integer up to $k^k$ can be realized as the number of spanning <em>arborescences</em> with a fixed root in a <em>digraph</em> on $3k-3$ vertices without multiple arcs.</p> </blockquote> <p>In other words, $\alpha(n)$ for digraphs is bounded by $O(\log n/\log\log n)$. Much better than what is known for undirected graphs, settling the conjecture at least for directed graphs.</p> <p>The next remaining open challenge is to investigate $\beta(n)$ for <em>symmetric matrices</em>.</p> http://mathoverflow.net/questions/93656/minimal-graphs-with-a-prescribed-number-of-spanning-trees/122149#122149 Answer by Aaron Meyerowitz for Minimal graphs with a prescribed number of spanning trees Aaron Meyerowitz 2013-02-18T09:08:57Z 2013-02-18T09:08:57Z <p>While the theta construction (paths of lengths $a,b$ and $c$ with common endpoints) is not optimal, how bad can it be? Well the <em>best</em> it could be with real numbers instead of integers is $a+b+c=\sqrt{3}\sqrt{n}.$ I'd guess, based on limited evidence that using the theta construction one can always obtain $\alpha(p) \lt 2\sqrt{p}$ (say for $p \gt 1000$) In other words, $\frac{(a+b+c)^2}{p} \lt 4$</p> <p>I looked at sets $\{a,b,c\}$ with members less than $101$ and pairwise co-prime (since I was aiming for primes). The only primes under $12500$ which I failed to get were $13,37,9463.$ For $n=9463$ there is $a,b,c=35,41,108$ with $\frac{(a+b+c)^2}{p} \approx 3.51.$ There are $1324$ primes $(1000 \lt p \lt 12500.)$ There are thirteen prime in this range with $\frac{(a+b+c)^2}{p} \gt 3.5.$ The other twelve are</p> <p>$\small [1657, {3, 31, 46}, 3.862], [2293, {11, 23, 60}, 3.853], [4093, {11, 38, 75}, 3.757], [1093, {5, 21, 38}, 3.747],$$\small [4513, {17, 32, 81}, 3.745], [1777, {6, 31, 43}, 3.602], [1297, {6, 25, 37}, 3.565], [1153, {11, 15, 38}, 3.552],$$\small [1549, {7, 27, 40}, 3.535], [4657, {22, 31, 75}, 3.518], [7129, {24, 43, 91}, 3.502], [3457, {19, 27, 64}, 3.500]$</p> <p>There are another twelve with the ratio in $(3.4,3.5).$ And $894$ of these primes (slightly more than $2/3$ ) have the ratio under $3.1.$ </p>