Counting Linear Extensions Below the $2^n$ Barrier
candidateconfidence 50%
VibeMathed reports this item as candidate. VibeMath preserves that report as a source assertion and has not independently authored a plain-language mathematical explanation.
Precise statement
Koivisto asked at Dagstuhl in 2013 whether the linear extensions of an arbitrary $n$-element poset can be counted exactly in time $O^*(c^n)$ for some $c < 2$. Yes: a deterministic exact algorithm runs in $O^*(1.89^n)$, breaking the $2^n$ barrier for the general problem.
The source statement is reproduced for indexing with attribution. Mathematical correctness requires domain-expert or mechanical review. VibeMath has not independently audited statement
fidelity, correctness, priority, or novelty.
What AI did
Claude Opus 5, ChatGPT 5.6 Sol
The paper's disclosure: "The core mathematical ideas underlying the new part of the algorithm and proof were discovered by Claude Opus 5 (Anthropic) during AI-assisted mathematical exploration" - naming the first-upper-element pattern representation, multiplicity-profile decoding, the deadline dynamic program and the state-counting strategy of Sections 3 to 5. The chain-partition bound of Section 2 refines Kozma and is not new. The research prompt supplied to Claude Opus 5 was itself generated by ChatGPT 5.6 Sol, modelled on OpenAI's publicly released prompt for their cycle double cover work.
Checked by this site on 21 August 2026 against the paper (arXiv:2608.19505v1): the disclosure is verbatim as quoted and Koivisto's Dagstuhl 2013 question is cited in the abstract. This is an exact deterministic algorithm with a proved worst-case bound, not a heuristic, so it clears the methodology's exclusion. The ancillary Python script cross-checks correctness against brute force on small posets and does not certify the running time; it was not re-run here. Days-old preprint, no independent review.
Breaking the $2^n$ Barrier for Counting Linear Extensions with a Short Elementary Algorithm
VibeMathed reports this item as candidate. VibeMath preserves that report as a source assertion and has not independently authored a plain-language mathematical explanation.
Known method families
argument (source-reported)
Source-reported tools: argument.
Independent: unknown · difference confidence: 0
What remains uncertain
VibeMath has not independently audited the mathematical statement, proof, or novelty claim.
The source status is candidate and must not be represented as solved.
VibeMath has not independently verified the mathematical claim.
AI-attempt independence and training-data exposure are unknown unless explicitly documented.
VibeMath has not independently audited the mathematical statement, proof, or novelty claim.