Logarithmic basis number of graphs and regular matroids
Abstract
The basis number bn(G) of a graph G is the minimum edge-congestion of a basis of its cycle space. We prove that every finite n-vertex multigraph satisfies bn(G)=O(log n), resolving, for simple graphs, a question of Bazargani, Biedl, Bose, Maheshwari and Miraftab, subsequently stated as a conjecture by Miraftab, Morin and Yuditsky. The argument also yields the cycle-rank refinement bn(G)=O(log β(G)), where β(G) is the dimension of the cycle space, and a reduction of Lehner and Miraftab, based on a theorem of Richter and Shank, then gives bn(G)=O(log g) for graphs of Euler genus g. For regular matroids we prove the ground-set bound bn(M)=O(log m), where m=|E(M)|, and logarithmic bounds in both the rank r(M) and the cycle-space dimension d. All these orders are best possible.
Related
- An inequality for the number of independent sets of matroids with an application to the forest-tree ratio of graphs
- Tree-independence number VIII. 3PC-free graphs have logarithmic tree-independence number
- A sharp upper bound on the number of spanning forests of regular graphs
- The Alon-Tarsi number of 4-regular circulant graphs
- The maximum number of triangles in regular graphs
BibTeX
@misc{knauer2026logarithmic,
title = {{Logarithmic basis number of graphs and regular matroids}},
author = {Kolja Knauer},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.02080},
eprint = {2609.02080},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.02080},
}
RIS
TY - UNPB
TI - Logarithmic basis number of graphs and regular matroids
AU - Kolja Knauer
PY - 2026
DA - 2026/09/14
PB - arXiv
DO - 10.48550/arxiv.2609.02080
UR - https://arxiv.org/abs/2609.02080
AB - The basis number bn(G) of a graph G is the minimum edge-congestion of a basis of its cycle space. We prove that every finite n-vertex multigraph satisfies bn(G)=O(log n), resolving, for simple graphs, a question of Bazargani, Biedl, Bose, Maheshwari and Miraftab, subsequently stated as a conjecture by Miraftab, Morin and Yuditsky. The argument also yields the cycle-rank refinement bn(G)=O(log β(G)), where β(G) is the dimension of the cycle space, and a reduction of Lehner and Miraftab, based on a theorem of Richter and Shank, then gives bn(G)=O(log g) for graphs of Euler genus g. For regular matroids we prove the ground-set bound bn(M)=O(log m), where m=|E(M)|, and logarithmic bounds in both the rank r(M) and the cycle-space dimension d. All these orders are best possible.
ER -