← All problems

Asymptotic ratio conjecture for spanning trees of suitable graphs

8 years old · documented by

Let Jn,mJ_{n,m} be the graph whose number of spanning trees is denoted by σ(Jn,m)\sigma(J_{n,m}), and let n,meinNn,m ein\mathbb{N} with fixed n≥2n\geq 2. Define

an,m=σ(Jn,m+1)σ(Jn,m).a_{n,m}=\frac{\sigma(J_{n,m+1})}{\sigma(J_{n,m})}.

Asymptotic ratio conjecture. The limit exists:

lim⁡m→+∞an,m=δn,\lim_{m\to +\infty}a_{n,m}=\delta_n,

where δn∈R\delta_n\in\mathbb{R}. Moreover,

σ(Jn,m)=(δn)m−3σ(Jn,3).\sigma(J_{n,m})=(\delta_n)^{m-3}\sigma(J_{n,3}).

The conjecture proposes a limiting multiplicative growth rate for the number of spanning trees as the second graph parameter tends to infinity. The preceding numerical values suggest this behavior for n=2n=2 and n=3n=3, but no proof or resolution is supplied in the source.

References

2 papers in this index state this conjecture (2017). The statement above is taken from the most recent of them; the others are arXiv:1701.08335.

Source: Maurizio Imbesi, Monica La Barbiera and Santo Saraceno, “Algorithmic releases on the spanning trees of suitable graphs”, arXiv:1704.04892 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.