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

From papers

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.

Progress summary

Solved

A 2019 paper gives a bijective proof of the conjecture, so the formula is now settled.

The conjecture was posed in 2016 as a $q$ -analogue of an earlier enumeration, with computer verification through $s=10$ . It asserts the stated generating-function identity for every $s \ge 1$ .

Known results

Computational verification for $s \le 10$ was reported in the 2016 source.

2019 bijective proof

A 2019 paper proves the identity for all $s \ge 1$ as Theorem 3.2. Its map to subsets of $\{1,3,\ldots,2s-3\}$ is bijective and records the inversion number as $(2s-1)(s-1)+|\eta(\pi)|$ , which immediately yields the factor $(1+q)^{s-1}$ . No counterexample, withdrawal, or substantive objection was found.

Current status (as of August 2026): The conjecture is resolved by the 2019 arXiv proof, with no recorded standing objection; no further open case remains.

Sources

Sources & referencesView supporting material

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).

1 week ago

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.

0 endorsements

Samuel Schlesinger · 4 days ago