Minimal graphs with a prescribed number of spanning trees

Question

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!

Answer 1

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

Answer 2

The conjecture has been proved in Spanning trees and continued fractions by Swee Hong Chan, Alex Kontorovich and Igor Pak.

The summary of the proof due to the second author:

We reduce the graph question to a question in Diophantine geometry, that smells a lot like Zaremba’s conjecture.

A decade ago, Bourgain and I made some progress on that problem, and that work (which has been extended now by Frolenkov, Huang, and especially Kan) applies to this context. It turns out that a key role is played by the Hausdorff dimension of a certain fractal, which needs to overcome a threshold value. The Diophantine problem is thus reduced to one in Thermodynamics.

To resolve the Thermodynamics, we have to rigorously compute this dimension, and (very luckily for us!) it turns out to indeed exceed the threshold, but just barely, in the hundredths place.

Answer 3

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

Answer 4

Since the picture in the original question is not working, and I don't know how far it extended anyway, I'm sharing this picture showing how the exact value of $\alpha(n)$ grows up to $n=6\,000\,000$. The curve is in fact a moving average over 100 consecutive points (otherwise it is too wildly oscillating to see).

This was brute-force computed by inspecting all graphs of at most $11$ vertices and counting their spanning trees with Kirchoff's matrix tree theorem. There are interesting oscillations but the rough growth seems logarithmic.