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

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, but 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 $O(k^2)$ 3k-3$ vertices without multiple arcs.

In other words, $\alpha(n)$ for digraphs is bounded by $O(\log n/\log\log n)^2$n)$. Much better than what is known for undirected graphs, but not yet close to settling the conjecture at least for directed graphs.

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

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, but 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. Thus:

Every integer up to $k^k$ can be realized as the number of spanning arborescences with a fixed root in a digraph on $O(k^2)$ vertices.

In other words, $\alpha(n)$ for digraphs is bounded by $O(\log n/\log\log n)^2$. Much better than what is known for undirected graphs, but not yet close to the conjecture.

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

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

Are any bounds known about THIS question?