MathDB

Bencs–Csikvári spanning-forest conjecture

For every integer r≥3r\ge 3 and every simple rr-regular graph GG on n=∣V(G)∣n=|V(G)| vertices, if F(G)F(G) denotes the number of spanning forests of GG, then F(G)1/n≤(r−1)r−1(r2−2r−1)r/2−1F(G)^{1/n}\le \dfrac{(r-1)^{r-1}}{(r^2-2r-1)^{r/2-1}}.

References

Primary source

arXiv

Additional references

enumerative-combinatoricsgraph-theoryspectral-graph-theory
Posted · edited

Progress summary

Refreshed
Claimed solved

A new preprint claims to prove the sharp spanning-forest bound for all regular graphs, but the claim has not been independently checked.

The Bencs–Csikvári conjecture predicts a sharp upper bound for the number of spanning forests in every dd-regular graph with d≥3d \ge 3. Bencs and Csikvári formulated it in their 2023 paper and explicitly left it unproved.

Known results

  • Bencs and Csikvári (2023) proved the weaker bound F(G)≤dnF(G)\le d^n.
  • Bencs and Csikvári (2023) showed that the conjectured exponential rate is attained asymptotically by high-girth dd-regular graphs.
  • Borbényi, Csikvári, and Luo (2020) proved the exact extremal value for d=3d=3 and improved bounds for 4≤d≤94\le d\le 9.
  • Borbényi, Csikvári, and Luo showed that a negative-correlation conjecture would imply the general conjecture.

October 2026 claimed resolution

T. Wu, S. Lu, and X. Dong claim the sharp upper bound for every rr-regular graph with r≥3r\ge 3 in a new arXiv preprint. The claim is unrefereed and has no independent mathematical corroboration in the retrieved sources.

Current status (as of October 2026): The conjecture is claimed solved by an unrefereed preprint, but the claimed proof remains unverified; the earlier partial results are established.

Sources

Solutions 0

No solutions have been posted yet.