{"id":"arxiv/2609.02080","url":"https://arxiv.org/abs/2609.02080","tags":["math.CO","cs.DM"],"score":0,"title":"Logarithmic basis number of graphs and regular matroids","domain":"math.CO","source":"arxiv","authors":["Kolja Knauer"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-02","reactions":{}}