Abstract:For a graph $G$, let $\tau(G)$ denote the number of spanning trees. We show that for every fixed $0 < c < 1/4$, the number of distinct values of $\tau(G)$, as $G$ ranges over simple graphs on $n$ vertices, is at least $\exp(c n \log n)$ for all sufficiently large $n$. This is optimal up to the choice of the constant $c$ and resolves a conjecture of Chan-Kontorovich-Pak regarding a problem of Sedláček from the late 1960s.
| Subjects: | Combinatorics (math.CO) |
| Cite as: | arXiv:2605.25088 [math.CO] |
| (or arXiv:2605.25088v1 [math.CO] for this version) | |
| https://doi.org/10.48550/arXiv.2605.25088 arXiv-issued DOI via DataCite (pending registration) |
From: Vishesh Jain [view email]
[v1]
Sun, 24 May 2026 14:05:26 UTC (22 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。