The height-two poset linear-extension almost-completeness conjecture
The height-two poset linear-extension almost-completeness conjecture
Let be the number of linear extensions of a finite poset , and let denote its restriction to posets of height two. Write for the set of values attained by . Height-two linear-extension conjecture. The function is almost complete, meaning that its value set contains all but finitely many positive integers. Numerical evidence exhibits many missing values, but height-two posets have sufficiently many possible inputs and the restricted function can attain large primes, so the conjecture remains plausible and open.
Sources & referencesView supporting material
Primary source
Swee Hong Chan and Igor Pak, “Computational complexity of counting coincidences”, arXiv:2308.10214 (2024).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.