Let EN_s,t(sigma)(q) denote the inversion-generating function for pattern-avoiding linear extensions of the rectangular poset with parameters s,t. The 2143 two-column inversion generating-function conjecture. For all s ≥ 1, EN_s,2(2143)(q) = q^(2s-1)(s-1) (1+q)^s-1. This is described as a q-analogue of a previously proved enumeration and is supported by computer-generated data for s ≤ 10; the general assertion remains open.

The 2143 two-column inversion generating-function conjecture

About 10 years old · traced to 2016

Let $EN_{s,t}(\sigma)(q)$ denote the inversion-generating function for pattern-avoiding linear extensions of the rectangular poset with parameters $s,t$ . The 2143 two-column inversion generating-function conjecture. For all $s \ge 1$ ,

EN_{s,2}(2143)(q) = q^{(2s-1)(s-1)} (1+q)^{s-1}.

This is described as a $q$ -analogue of a previously proved enumeration and is supported by computer-generated data for $s \le 10$ ; the general assertion remains open.

References

Primary source

David Anderson, Eric S. Egge, Manda Riehl, Lucas Ryan, Ruth Steinke and Yuriko Vaughan, “Pattern Avoiding Linear Extensions of Rectangular Posets”, arXiv:1605.06825 (2016).

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed progress

A 2019 paper claims a complete proof of the formula, so no case is known to remain open, but this report does not independently verify it.

The conjecture was posed in 2016 by Anderson, Egge, Riehl, Ryan, Steinke, and Vaughan as a $q$ -analogue of an earlier enumeration, with data supporting it through $s=10$ .

2019 proof

Colin Defant’s paper states the identity as Theorem 3.2 for every $s\geq 1$ . Its bijection to subsets of $\{1,3,\ldots,2s-3\}$ gives $\operatorname{inv}(\pi)=(2s-1)(s-1)+|X|$ , yielding $EN_{s,2}(2143)(q)=q^{(2s-1)(s-1)}(1+q)^{s-1}$ .

Community submission (unverified)

A submitted proof reproduces Defant’s bijection and derivation, and points to Theorem 3.2 and its published version. The submission itself is unverified.

Current status (as of September 2026): The formula is presented as proved for all $s\geq 1$ by Defant’s 2019 theorem, but the automated report treats that resolution as unverified.

Sources

ProofThis solution needs a summarySee full solutionHide full solution

This conjecture was proved by Colin Defant in Theorem 3.2 of “Proofs of Conjectures about Pattern-Avoiding Linear Extensions”:

https://arxiv.org/abs/1905.02309

Published version:

https://doi.org/10.23638/DMTCS-21-4-16

Here is the bijective argument. Let

\mathcal S_s=\mathcal P(\{1,3,5,\ldots,2s-3\}).

Defant defines

\eta:EN_{s,2}(2143)\longrightarrow\mathcal S_s

\eta(\pi) = \{i\in\{1,3,5,\ldots,2s-3\}:i+3\text{ occurs before }i\text{ in }\pi\}.

The proof shows that $\eta$ is a bijection and that it tracks inversions by

\operatorname{inv}(\pi) = (2s-1)(s-1)+|\eta(\pi)|.

Consequently,

\begin{aligned} EN_{s,2}(2143)(q) &=\sum_{X\subseteq\{1,3,\ldots,2s-3\}} q^{(2s-1)(s-1)+|X|}\\ &=q^{(2s-1)(s-1)} \sum_{k=0}^{s-1}\binom{s-1}{k}q^k\\ &=q^{(2s-1)(s-1)}(1+q)^{s-1}. \end{aligned}

This is exactly Conjecture 7.2 of the original source and exactly the statement of MathDB #333177. Therefore the entry should be marked solved.