Return to 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!

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!

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})$$

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!

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!

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})$$

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!

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})$$

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!