PreprintCC BY-NC-ND 4.0arXiv
An inequality for the number of independent sets of matroids with an application to the forest-tree ratio of graphs
Abstract
Let M=(E,ℐ) be a matroid of rank r. Let ℐk be the independent sets of size k, and let Ik=|ℐk| and I=|ℐ|. We show that if every set F∈ ℐr−1 is contained in at least δ bases, then ln (I/Ir)geqslant (Ir−1)/Ir· δln (1+1/δ). In particular, we have I/Irgeqslant 2Ir−1/Ir. By combining this result with several other ideas, we prove that if G is a simple connected graph on n vertices, and F(G) and T(G) denote its numbers of spanning forests and spanning trees, respectively, then F(G)/T(G)geqslant F(Kn)/T(Kn), where Kn is the complete graph on n vertices. Equality holds if and only if G=Kn.
Related
- A Sharp Basis-Mass Inequality for Binary Matroids without a Fano Minor
- A note on the list chromatic number of two matroids
- Logarithmic basis number of graphs and regular matroids
- A Khintchine type inequality for non-independent random variables
- An independent proof of the even-dimensional S-matrix inequality
BibTeX
@misc{bencs2026inequality,
title = {{An inequality for the number of independent sets of matroids with an application to the forest-tree ratio of graphs}},
author = {Ferenc Bencs and Péter Csikvári},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.18611},
eprint = {2609.18611},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.18611},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - An inequality for the number of independent sets of matroids with an application to the forest-tree ratio of graphs
AU - Ferenc Bencs
AU - Péter Csikvári
PY - 2026
DA - 2026/09/16
PB - arXiv
DO - 10.48550/arxiv.2609.18611
UR - https://arxiv.org/abs/2609.18611
AB - Let M=(E,ℐ) be a matroid of rank r. Let ℐ_k be the independent sets of size k, and let I_k=|ℐ_k| and I=|ℐ|. We show that if every set F∈ ℐ_r−1 is contained in at least δ bases, then ln (I/I_r)geqslant (I_r−1)/I_r· δln (1+1/δ). In particular, we have I/I_rgeqslant 2^I_r−1/I_r. By combining this result with several other ideas, we prove that if G is a simple connected graph on n vertices, and F(G) and T(G) denote its numbers of spanning forests and spanning trees, respectively, then F(G)/T(G)geqslant F(K_n)/T(K_n), where K_n is the complete graph on n vertices. Equality holds if and only if G=K_n.
ER -