Source-linked AI summary
Logarithmic basis number of graphs
Kolja Knauer
TL;DR
The paper studies how small the edge-congestion of a cycle-space basis can be for finite multigraphs. It combines randomized rounding with a reduction to simple graphs to prove logarithmic upper bounds in graph size and cycle rank, with matching lower-bound orders.
Problem
The paper addresses bounding the basis number bn(G), the minimum edge-congestion of a cycle-space basis, for finite multigraphs.
Method
The argument rounds fractional mass bounds to a genuine base with controlled intersections and reduces multigraphs to simple graphs while preserving the relevant cycle-space structure.
Results
bn(G)=O(log n) for n-vertex finite multigraphs and bn(G)=O(log β(G)) for graphs with cycle rank β(G); the matching lower-bound orders are known.
Takeaways & Limitations
The logarithmic orders are best possible, with lower bounds of Ω(log n), Ω(log β), and logarithmic genus order established by prior results.
Takeaways & Limitations
The paper allows loops and parallel edges and uses log for base-2 logarithms and ln for natural logarithms.
Abstract
from arXiv · showhide
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.
1. Introduction
The paper studies the basis number, the minimum edge-congestion of a cycle basis, and improves prior logarithmic-squared bounds to logarithmic bounds in vertex count, cycle rank, and Euler genus. These bounds match known lower-bound orders.
- Definitions: The basis number bn(G) is the minimum edge-congestion among cycle bases, with congestion measuring the maximum number of basis elements containing any edge.The paper distinguishes congestion from the charge of an individual edge and notes equivalent terminology in prior work.
- Prior bounds: Prior work established O(log^2 n) for simple n-vertex graphs, while Bazargani et al. posed O(log n) and Miraftab et al. stated it as a conjecture.
- Main results: O(log n) congestion holds for every finite multigraph on n ≥2 vertices, resolving the general n-vertex problem.
- Main results: O(log β(G)) congestion holds for finite multigraphs with cycle rank β(G) ≥2, where β(G) is the cycle-space dimension.The cycle rank is also called the first Betti number and satisfies β(G)=|E(G)|−|V(G)|+c(G).
- Main results: O(log g) congestion holds for graphs of Euler genus g ≥2, closing the exponent gap between the prior O(log^2 g) upper bound and Ω(log g) lower bound.The genus result uses a reduction of Lehner and Miraftab based on a theorem of Richter and Shank.
- Optimality: The logarithmic orders are best possible: known constructions give Ω(log n), Ω(log β), and Ω(log g) lower bounds.
2. Cycle bases and two external ingredients
The section introduces weighted cycle-basis control and dependent rounding as the two ingredients used to obtain simultaneous low edge congestion.
- Conventions: The paper permits loops and parallel edges, and distinguishes base-2 logarithms from natural logarithms.A loop contributes two to the degree of its incident vertex.
- Weighted control: Rizzi’s theorem gives a cycle basis whose total weighted charge is at most a log n when edge weights total W.The basis can additionally be chosen weakly fundamental, though only the weight bound is used here.
- Fractional bases: A fractional base is a point in the matroid base polytope, equivalently a probability distribution on bases with matching marginal probabilities.The base polytope is the convex hull of incidence vectors of matroid bases.
- Dependent rounding: Randomized swap rounding converts a fractional base into one random base while preserving marginal probabilities and retaining Chernoff upper-tail bounds.These tail bounds control the simultaneous intersection of the rounded base with several specified sets.
- Simultaneous rounding: If q sets each have fractional mass at most L, simultaneous rounding yields a genuine base meeting every set in O(L + log q) elements.A union bound gives positive probability that all q inequalities hold simultaneously.
- Simultaneous rounding: The almost-additive O(L + log q) bound is stronger in the application because L = O(log n) and q = O(n^2).A sharper L log q log log q estimate applies when L = O(1), but not in this parameter regime.
3. From weighted average charge to low congestion
The proof applies linear-programming duality to weighted cycle-basis bounds, then uses matroid structure and simultaneous rounding to obtain a single basis with logarithmic congestion.
- Weighted average charge: Linear-programming duality produces a probability distribution on cycle bases whose expected charge for every edge is at most a log n.For each edge, the charge is averaged over the distribution, while the weighted theorem supplies the dual bound.
- Matroid formulation: A connected simple graph’s simple-cycle bases are the bases of a vector matroid defined by independence over F2.This matroid structure makes the rounding lemma applicable to cycle bases.
- Simple-graph result: Every connected simple graph on n ≥ 2 vertices satisfies bn(G) ≤ C0 log n.Trees are immediate, while graphs containing cycles follow from the matroid-rounding construction.
- Rounding to one basis: The simultaneous rounding lemma converts these expected edge charges into one cycle basis with logarithmic congestion.The sets used in rounding correspond to the cycles containing each graph edge.
- Extension to multigraphs: Deleting loops and retaining one representative from each non-loop parallel class reduces a multigraph to a simple graph without increasing the final order beyond O(log n).Parallel copies can be restored with basis number bounded by the maximum of the old basis number and 2; loops add independent one-edge cycles.
4. The cycle-rank bound
The cycle-rank refinement reduces the graph to a smaller multigraph by deleting bridges and suppressing degree-two vertices, preserving both cycle rank and basis number.
- Reduction: Bridges can be deleted without changing the basis number, so the proof reduces to connected components containing cycles.The component’s cycle rank is at most the original graph’s cycle rank.
- Series reduction: Suppressing a degree-two vertex preserves both basis number and cycle rank.The replacement edge may be a loop when the two neighbors coincide.
- Size bound: After suppression, a nontrivial reduced component has minimum degree at least three and at most 2r − 2 vertices when its cycle rank is at most r.This follows from rK = mH − nH + 1 and 3nH ≤ 2mH.
- Conclusion: Applying the vertex bound to the reduced components and taking their maximum yields the cycle-rank theorem.The one-vertex case consists only of loops and has basis number at most 1.
5. Graphs on surfaces
The paper reduces graphs embedded on surfaces to subgraphs whose cycle rank is controlled by the surface's Euler characteristic, yielding logarithmic basis-number bounds in Euler genus. The argument also reconciles orientable and non-orientable genus conventions and contrasts its bound with an earlier weaker recursive estimate.
- Genus conventions: Euler genus equals 2h for orientable genus h and h for non-orientable genus h.Thus the same logarithmic asymptotic bound applies under either genus convention.
- Topological reduction: Every connected graph has a cellular embedding in a surface of minimum Euler genus.This permits choosing a cellular embedding that realizes the graph's Euler genus before applying the reduction.
- Topological reduction: β(H) = 2 −χ(Σ) and bn(G) ≤bn(H) + 2.Lemma 5.1 provides the key topological reduction for a connected graph with a 2-cell embedding.
- Euler-genus bound: bn(G) = O(log g) for graphs of Euler genus g.For a connected graph, the proof chooses a cellular embedding of Euler genus g and applies Lemma 5.1 followed by Theorem 1.2.
- Euler-genus bound: Components of Euler genus at most one have basis number at most three, while every other component has Euler genus at most g.Componentwise cycle bases extend the bound to disconnected graphs.
- Related work: Lehner and Miraftab's recursive use of the reduction led to O(log2 g), whereas the present argument gives a logarithmic bound in g.The remark records the earlier recursive approach and its weaker asymptotic form.
6. A matroidal question
The cycle-rank result motivates extending logarithmic circuit-basis congestion bounds from graphs to binary matroids. The paper poses this as an open question for regular matroids and other natural subclasses.
- Motivation: The graphic case is exactly the studied parameter, motivating extensions of Theorem 1.2 beyond graphs.The discussion frames circuit bases of binary matroids as the natural setting for this generalization.
- Open question: Question 6.1 asks whether every regular matroid with dim Z(M) ≥2 has a circuit basis with bounded element congestion.The proposed bound uses an absolute constant C.
- Open question: More generally, the paper asks which natural subclasses of binary matroids admit a logarithmic bound in cycle-space dimension.This broadens the regular-matroid question to other subclasses.
7. Statement of AI use
The author reports using OpenAI's GPT-5.6 Sol as a research aid for proof exploration, literature searches, and manuscript drafting and revision. The author states that the arguments and references were independently checked and assumes responsibility for the final content.
- AI use: OpenAI's GPT-5.6 Sol assisted with proof strategies, literature searches, and manuscript drafting and revision.The stated use was as a research aid.
- AI use: The author independently checked the arguments and references and takes full responsibility for mathematical correctness and final content.This is the author's stated accountability statement.