VibeMathedMath problems solved with AI
Sign in

Logarithmic basis number of graphs

The basis number bn(G)\mathrm{bn}(G) of a graph GG is the minimum edge-congestion of a basis of its cycle space. We prove that every finite nn-vertex multigraph satisfiesbn(G)=O(log⁡n),\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 refinementbn(G)=O(log⁡β(G)),\mathrm{bn}(G)=O(\log \beta(G)),where β(G)\beta(G) is the dimension of the cycle space, and a reduction of Lehner and Miraftab, based on a theorem of Richter and Shank, then givesbn(G)=O(log⁡g)\mathrm{bn}(G)=O(\log g)for graphs of Euler genus gg. These orders are best possible.

Result
Proved(see note)
Status
Resolved
AI contribution
AI co-developed
Method
Argument
Field
Graph theory
Posed by
Bazargani, Biedl, Bose, Maheshwari and Miraftab
Year posed
2024
Years open
2y
Solved
2026-09-02
Model
ChatGPT-5.6 Sol
Vendor
OpenAI
Collaborators
Kolja Knauer
Verification
Unreviewed
Publication
Preprint
Significance
15 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Knauer proves that every finite nn-vertex multigraph satisfies bn(G)=O(log⁡n)\mathrm{bn}(G)=O(\log n), improving the previous general O(log⁡2n)O(\log^2 n) bound and matching the known Ω(log⁡n)\Omega(\log n) order. He also proves the sharper cycle-rank bound bn(G)=O(log⁡β(G))\mathrm{bn}(G)=O(\log\beta(G)). Combined with a reduction of Lehner and Miraftab, this yields bn(G)=O(log⁡g)\mathrm{bn}(G)=O(\log g) for graphs of Euler genus gg, improving the previous O(log⁡2g)O(\log^2 g) bound to the optimal logarithmic order.

What the AI did

The proof was found with the help of GPT-5.6 Sol. The model was also used to explore proof strategies, locate potentially relevant literature, and assist with drafting and revising the manuscript. Knauer independently checked the arguments and references and takes responsibility for the final result.

Verification

Unreviewed. A nine-page preprint one day old at submission, with no peer review and no formal verification. The argument is conventional and self-contained - weighted cycle-basis bounds, minimax duality and dependent randomized rounding - so it is readable by any combinatorialist, and the author states he checked the arguments and references himself. Nobody independent has.

Sources

Submitted by VibeGene on

Changelog2 changes

Discussion