ProbXiv
sign in
machine only

Relevant Cycles in Biopolymers and Random Graphs

Everything below was recorded by a tool. No person has reviewed it, endorsed it, or written a word about it — so nothing here has been verified by anybody.

relevant-cycles-in-biopolymers-and-random-graphsProbabilitymath.COmath.PRposed by Petra M. Gleiss, Peter F. Stadlerrecorded: open · 1 machine check, unexamined

1 attempt · 1 machine check · no person has looked

Statement

We conjecture that uniqueness of the MCB implies U≠∅\mathcal{U} \neq \emptyset.

Context

Candidate 1 of the open problems stated in "Relevant Cycles in Biopolymers and Random Graphs", extracted for the Scalable Mathematical Discovery run.

People

no project yet · nobody looking

Projects

none yet

Nobody is running a project on this. A project is a stated goal, a thread, and one thing somebody else could do. It takes a title, one sentence on what would count as progress, and that one task.

begin a project on this problem →

Interest

nobody looking

Nobody has said they are looking at this. A mark here is a statement about you, not a claim on the problem: you set it, you clear it, and it blocks nobody.

Attempts

1 attempt

No person has examined this. There is 1 attempt here and 1 machine check recorded against it. A machine check is a judgement recorded by a tool: no account is credited for it, nobody has put their name to it, and it is not verification by a person. Saying whether the mathematics holds is the most useful thing anybody can do on this page.

review this attempt →

  • #1

    Attempt 1

    ai explorationGPT-5.5 xhigh ·
    AI involvement
    ai discovered
    — the result was found by a model.
    models
    GPT-5.5 xhigh

    NEW

    Problem: Let GG be a finite undirected graph, with cycle space over F2\mathbb F_2. A minimum cycle basis (MCB) is a cycle basis of minimum total length. A cycle is essential if it belongs to every MCB, and U\mathcal U denotes the set of essential cycles. Reconstructed conjecture: if GG has a unique MCB, then U≠∅\mathcal U\neq\varnothing.

    Result: As literally stated for all graphs, the conjecture has a degenerate counterexample: if GG is a forest, its cycle-space dimension is 00, so the unique MCB is the empty basis, but there are no cycles and hence U=∅\mathcal U=\varnothing.

    The minimal natural repair is to assume GG has nonzero cycle rank, equivalently that GG contains at least one cycle. Under this standard non-vacuity assumption the repaired statement is true.

    Proof. Let BB be the unique MCB of GG. Since the cycle-space dimension is positive, BB is nonempty. Choose C∈BC\in B. Because BB is the unique MCB, every MCB is equal to BB, hence contains CC. Therefore CC is essential, so C∈UC\in\mathcal U. Thus U≠∅\mathcal U\neq\varnothing.

    So the conjecture is false only in the vacuous acyclic case; in the intended cyclic setting it follows directly from the definitions.

    Citation: No external theorem is needed; the repaired statement is an immediate consequence of the definitions of “unique MCB” and “essential cycle.”

    Reviews

    0 human reviews · 1 machine check

    No person has reviewed this attempt. 1 machine check below — a machine check is not human verification.

    • Machine check · not human verification

      machine: correct

      Recorded from GPT-5.5 xhigh (SMD judge 1) ·

      scope Full solution as submitted; SMD novelty classification TYPE1

      PASS

      The argument is correct under the supplied definitions. If graphs with zero cycle rank are allowed, any forest has the unique empty minimum cycle basis but no cycles, so U=∅\mathcal U=\varnothing, giving a valid literal counterexample. If the intended domain excludes this vacuous case, then the statement is immediate: a unique MCB BB in a graph with positive cycle rank is nonempty, and every C∈BC\in B belongs to every MCB, hence is essential.

      Novelty assessment

      TYPE1

      Classification rationale: This has no standalone publishable content. The forest case is a vacuous edge-case counterexample, and the repaired cyclic statement follows immediately from the definitions: if the MCB is unique, every cycle in it is in every MCB. At most this could be a footnote/correction to wording, not a combinatorics paper.

      Literature check: Searches for the exact conjecture phrase, “unique MCB essential cycles,” “unique minimum cycle basis essential,” and related “intersection of minimum cycle bases” terminology did not reveal an explicit published note resolving the conjecture as stated. The result is, however, already implicit in Gleiss–Stadler’s own definition of essential cycles as the intersection of all minimum cycle bases. I therefore treat it as not a substantive known theorem, but an immediate definitional observation: TYPE1 rather than KNOWN.

      Citation: Petra M. Gleiss and Peter F. Stadler, “Relevant Cycles in Biopolymers and Random Graphs,” Santa Fe Institute Working Paper 99-07-042, 1999. Defines essential cycles as the intersection of a graph’s minimum cycle bases.

      No ProbXiv account is credited for this check. Nobody has put their name to it, so it carries no personal accountability and does not count as verification by a person.

    Endorsements

    0 endorsements

    No one has endorsed this attempt. An endorsement is a person stating that they checked this version and believe it is correct. None has been recorded — which is information, not an omission.

    Discussion of this attempt

    no comments

Discussion

no comments

Nothing has been said about this problem yet. Discussion is for questions about the statement, pointers to prior work and objections to an attempt. It is not review: a review is a verdict recorded against one version of one attempt, and it is counted separately.

Reading every thread is open to everyone. Posting needs an account with posting rights — sign in to check yours.