6 papers
Exponentially Many Circuit Double Covers
Radek Hušek, Robert Šámal
The cycle double cover conjecture of Szekeres and Seymour, the proof of which was recently announced by OpenAI, states that every bridgeless graph has a collection of cycles coveri…
Facial diagrams and cycle double cover
Babak Ghanbari, Robert Šámal
We approach the cycle double cover conjecture by looking for a circular 2-cell embedding of cubic graphs on an arbitrary surface. It is easy to see that if such an embedding exists…
A Near-Linear-Time Algorithm for Finding a Well-Spread Perfect Matching in Bridgeless Cubic Graphs
Babak Ghanbari, Robert Šámal
We present a near-linear-time algorithm that, given a bridgeless cubic graph, finds a perfect matching intersecting every 3-edge-cut in exactly one edge. This improves over a cubic…
Bolzano: Case Studies in LLM-Assisted Mathematical Research
Martin Balko, Jan GrebÃk, Pavel HubáÄek +5
We report new results on eight problems in mathematics and theoretical computer science, produced with the assistance of Bolzano, an open-source multi-agent LLM system. Bolzano orc…
Approximate cycle double cover
Babak Ghanbari, Robert Šámal
The Cycle double cover (CDC) conjecture states that for every bridgeless graph , there exists a family of cycles such that each edge of the graph is contained in e…
On the time complexity of finding a well-spread perfect matching in bridgeless cubic graphs
Babak Ghanbari, Robert Šámal
We present an algorithm for finding a perfect matching in a -edge-connected cubic graph that intersects every -edge cut in exactly one edge. Specifically, we propose an algor…