# Minimal graphs with a prescribed number of spanning trees

As its long ago since Erdő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.

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$ ?

Motivation. I was introduced to the question through this post 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)

What is known?

Sedlacek was able to show that for every (not so) large $n$

$\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}.$

Following is a summary of what I was able to find out.

Since the equation $n = ab+ac+bc$ is solvable for integers $1 \leq a < b < c$ for all but a finite number of integers $n$ (see this 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}$

$$\alpha(n) \leq \frac{n+9}{4}.$$

Moreover, the only fixed points of $\alpha$ are 3, 4, 5, 6, 7, 10, 13 and 22.

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 turns out 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 < \cdots < x_k.$

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

Conjecture.

$$\alpha(n) = o(\log{n})$$

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.

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!

Edit. If anyone is willing to work on this problem, I'd be glad to collaborate since I'd benefit much from it!

-
Suppose you tackle it from the other end: take complete graphs on alpha(n) vertices which have n spanning trees, remove edges, and see what coverage (values of different n) you get. I don't know about asymptotics, but you may be able to show your conjecture holds for all n off of a set of density 0. Gerhard "Ask Me About System Design" Paseman, 2012.04.10 –  Gerhard Paseman Apr 10 '12 at 18:45
Oh, if you are looking for alpha(p) where p is prime, it leads me to think that such graphs will have trivial automorphism group. If true, that would also be a nice result. Gerhard "Ask Me About System Design" Paseman, 2012.04.10 –  Gerhard Paseman Apr 10 '12 at 18:48
A cycle of length $p$ has $p$ spanning trees and an automorphism group of size $2p$. That's not the only example. –  Brendan McKay Apr 11 '12 at 1:28
Indeed, but I wonder about the case of large prime p and alpha(p) small. Is alpha(7) equal to 7? Gerhard "Ask Me About System Design" Paseman, 2012.04.10 –  Gerhard Paseman Apr 11 '12 at 4:14
$\alpha(7)$ is indeed 7. As you may see in the post, 3, 4, 5, 6, 7, 10, 13 22 are the (only) fixed points of $\alpha$! –  Jernej Apr 11 '12 at 8:45

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$.

For given $n$, what is the smallest $k=\beta(n)$ such that $n$ is the determinant of such a matrix?

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$.

Additions (incorporating the remark by Will Sawin): For example, $$\left| \begin {matrix} 4&7&1&3\cr -1&10&0&0 \cr 0&-1&10&0\cr 0&0&-1&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.

One can work this determinant into the number of directed spanning trees of a multigraph: $$\left| \begin {matrix} 4&-7&-1&-3\cr -1&10&0&0 \cr 0&-1&10&0\cr 0&0&-1&10 \end {matrix} \right| = 4000-713=3287.$$ Let us add a fifth column to make column sums zero: $$\begin {pmatrix} 4&-7&-1&-3\cr -1&10&0&0 \cr 0&-1&10&0\cr 0&0&-1&10\cr -3& -2&-8&-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.

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.)

Every integer up to $k^k$ can be realized as the number of spanning arborescences with a fixed root in a digraph on $3k-3$ vertices without multiple arcs.

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.

The next remaining open challenge is to investigate $\beta(n)$ for symmetric matrices.

-
You can get every number up to $k^k-1$ by putting the number in base $k$ notation, viewing that as a polynomial, using the standard constructing to make a matrix with that characteristic polynomial, and adding $k$ times the identity matrix and making sure the signs work out. Obviously $(k+1)^{k^2}$ is a bound on the other side. By the way, it seems like the inverse functions to $\alpha$ and $\beta$ are the simpler ones to consider and describe. –  Will Sawin Feb 17 '13 at 21:38
Very nice! your upper bound is far too generous, if that is what you meant. The Hadamard bound gives $k^{3k/2}$. –  Günter Rote Feb 17 '13 at 23:47

While the theta construction (paths of lengths $a,b$ and $c$ with common endpoints) is not optimal, how bad can it be? Well the best 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$

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

$\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]$

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.$

-