Counting linear extensions below the 2^n barrier
A deterministic algorithm counts the linear extensions of an arbitrary n-element poset in time O*(1.89^n), breaking the 2^n barrier for the general problem.
- Lab
- Independent
- Model
- Claude Opus 5; ChatGPT 5.6 Sol
- Field
- Computer science
- Date
- 2026-08-19
- Human collaborators
- Keigo Oka
- Problem posed
- 2013 · open 13 yrs
Sources
Original work
Independent commentary
What was found
A linear extension of a finite poset is a total order respecting it. The algorithm counts them exactly for an arbitrary n-element poset in O*(1.89^n) time, resolving a question posed by Koivisto at Dagstuhl in 2013. It refines an argument of Kozma for two-dimensional posets: a chain partition handles posets far from an antichain, and otherwise a maximum antichain is fixed and only the first comparable element above each of its elements is recorded, with a decoding lemma enumerating the resulting patterns from their multiplicities. Once a pattern is fixed each antichain element has a release condition and at most one deadline, so the dynamic program need only store how many elements are released in each deadline class.
Novelty check
The question is attributed to a specific venue and date, Koivisto at Dagstuhl 2013, and the 2^n barrier for the general problem is the standing baseline the paper names. The refinement is stated against a specific prior argument, Kozma's for two-dimensional posets, which makes the delta explicit. A verification script ships as an ancillary file with the preprint. No prior sub-2^n algorithm for the general problem appears.
Caveats and known objections
A preprint, unrefereed, with no independent check on record, and vibemathed lists it as a candidate pending review; the ancillary verification script is not a proof artifact and nothing is formalized. Autonomy is graded ai-led on an unusually layered disclosure: the core mathematical ideas behind the new part of the algorithm and proof are stated to have been discovered by Claude Opus 5, while the research prompt supplied to it was itself generated by ChatGPT 5.6 Sol, which the author instructed to model the prompt on OpenAI's publicly released one for the cycle double cover work, so the prompt-generation stage was AI-assisted as well. Generative tools were also used for literature search, drafting and verification assistance.
Also recorded at
vibemathedcounting-linear-extensions-below-two-to-the-n
Nothing mechanically. It is a parallel listing of the same result, carrying its own verification label rather than an independent check.
Nobody outside the lab has checked this yet.
Reading the primary source closely enough to say whether it supports the claim counts as a check, and you are credited on the entry.
Or on GitHub: submit a check challenge the grade send a correction or send a pull request
Flag this for triage
Signals order the review queue and nothing else. They are never published, and they never move a grade: that takes a citation.
Entry history (1 event)
- AddedEntered the registry graded Author verified and AI-led.
Entries are never deleted. A grade that does not hold up is downgraded on the record, with the reason beside it.
Graded author verified for verification and ai-led for autonomy. What these mean.
Cite this entry
whataifound.org. (2026). Counting linear extensions below the 2^n barrier. whataifound.org: A Registry of AI Scientific and Mathematical Discoveries. https://whataifound.org/finding/2026-08-19-linear-extensions-below-2nBibTeX
@misc{whataifound-independent-2026-2n,
title = {Counting linear extensions below the 2^n barrier},
author = {{whataifound.org}},
year = {2026},
howpublished = {whataifound.org: A Registry of AI Scientific and Mathematical Discoveries},
note = {Result by Independent. Verification: Author verified. Autonomy: AI-led.},
url = {https://whataifound.org/finding/2026-08-19-linear-extensions-below-2n}
}