Logarithmic basis number of graphs

Source abstract

The basis number $\mathrm{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 $$\mathrm{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 $$\mathrm{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 $$\mathrm{bn}(G)=O(\log g)$$ for graphs of Euler genus $g$. These orders are best possible.