Polynomial-time conjecture for counting constrained linear extensions

Let PP be a finite poset with fixed prescribed values represented by z,c\mathbf z,\mathbf c, and let Nz,c(P)N_{\mathbf z,\mathbf c}(P) denote the number of linear extensions satisfying those prescriptions. Constrained linear-extension counting conjecture. For every fixed integer mNm\in\mathbb N, the decision problem

{Nz,c(P)=m}\{N_{\mathbf z,\mathbf c}(P)=m\}

is in P{\mathsf P}. The source proves the case m=1m=1 and conjectures the statement for every fixed mm.

Sources & referencesView supporting material

Primary source

Swee Hong Chan and Igor Pak, “Linear extensions of finite posets”, arXiv:2311.02743 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.