As it's 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 known whether 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})$$
alt text http://shrani.si/f/1G/lc/2yL7fZJd/graf.png
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!
Best Answer
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$.
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$.
Are any bounds known about THIS question?
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.)
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.