Let $G$ be a graph. Following Wikipedia, a cycle basis is a set of simple cycles forming a basis for the cycle space of the graph.
I call the overlap of a cycle basis the maximum number of cycles shared by a single edge $e\in T$. Is there a general bound available for the minimum possible overlap over all cycle bases?
For example, if $G$ is planar, then one can find a cycle basis where each edge is contained in at most $2$ cycles (the faces of the cells formed by the planar embedding), so the minimum possible overlap is at most $2$.
What can be said for more general graphs?
For example, consider a graph $G=(V,E)$ with $V=\{0,1,\cdots,n+1\}$ and $E = \{(0,j) \mid 1\leq j n\} \cup \{(j,n+1) \mid 1\leq j\leq n\}$. The genus of $G$ is $n - 1$. Any fundamental cycle basis (one constructed from considering the cycles determined by a minimal spanning tree) has overlap $n-1$. However this graph is planar so as discussed above its minimal overlap for a cycle basis is at most $2$.
I would appreciate any thoughts about how to obtain a bound for this minimal overlap in general. Perhaps one can provide a reasonable bound in terms of the number of vertices in the graph, or a nontrivial bound in terms of the genus.
The trivial bound on the overlap is $m+n-1$, where $m$ is the number of edges and $n$ is the number of vertices. (This is how many cycles are in a cycle basis.) I can do better than that, but the improved bound is still embarrassingly high.
Consider the following algorithm for creating a cycle basis. As we go, we will keep track of how many times each edge has been used. On each step, we find an edge $e$ that has been used as many times as possible, and either:
At the end, we have a spanning tree and a cycle for each edge outside the spanning tree, so we have the right number of cycles. If we put their incidence vectors as rows in a matrix in the order we constructed them, with edges as columns in the order we deleted them, we get a matrix in row-echelon form where each cycle's pivot is the edge it was found for. So we get linear independence.
At each step, the number of times the most frequently used edge has been used increases by at most $1$. Suppose it reaches $k$ at some point. Then, before that point, we must have removed edges that were contained in $k-1, k-2, ..., 1$ cycles. The sum of these numbers is more than $k^2/2$.
But the sum of the number of cycles containing each edge is at most $mn$: there are fewer than $m$ cycles, each with at most $n$ edges. So $k^2/2<mn$, and the overlap is at most $\sqrt{2mn}$.
The best I can say in the opposite direction is that there are graphs with arbitrarily high overlap. For this, take a graph with girth $g$ and $m\ge 2n$; these have overlap at least $g(m+n-1)/m > g/2$. (A random 4-regular graph will work with a positive probability, provided $n$ is large enough.)