Diagonal realizability census for up-growing 2D presentations

Scope

Relabel each presentation by arrival order, so the elements arrive as $0,1,\ldots,n-1$. A pair of coordinate orders $(L_x,L_y)$ defines such a presentation exactly when their inversion sets relative to arrival are disjoint. The poset relations are the pairs $i<j$ inverted by neither order. Enumerating all such ordered permutation pairs is therefore exhaustive for naturally labeled (equivalently, up-growing presented) posets of dimension at most two.

For fixed $L_x,L_y$, let $g=(A_0,\ldots,A_{n-2}, B_0,\ldots,B_{n-2})$ be the consecutive positive coordinate gaps. If $D_i g=(x_{i+1}+y_{i+1})-(x_i+y_i)$, diagonal realizability is the homogeneous feasibility problem

$$g>0,\qquad Dg\ge 0.$$

It is equivalent to the normalized rational LP $g\ge1,\ Dg\ge0$. The checker uses a floating LP only to propose a point, reconstructs its coordinates as Fraction values, and verifies every inequality exactly.

Weak and strict diagonal realizability are equivalent here. Given a weak witness with gaps normalized to at least one, replacing

$$(x_i,y_i)\longmapsto \left(x_i+\frac{i}{2n},\,y_i+\frac{i}{2n}\right)$$

preserves both coordinate orders (each old coordinate gap changes by less than $1/2$) and makes successive diagonal sums strictly increase by an additional $1/n$. More generally, this perturbation argument also removes coordinate ties in an arbitrary weak dominance embedding if epsilon is chosen below every incomparable backward-coordinate margin divided by $2n$.

Exact census

The full nondecreasing census produced:

Every positive entry was backed by an exact rational witness. The two seven-element obstructions are order-dual/arrival-reversed copies. Thus the smallest obstruction has seven elements. This is a finite computer-exhaustive statement, not an asserted general classification theorem.

First seven-element obstruction

Let $P$ be the transitive closure of the covers

$$0<1<5,\qquad 0<6,\qquad 2<3,\quad2<5,\quad2<6,\qquad4<5,$$

presented in the order $0,1,2,3,4,5,6$. This is up-growing, has width four, and is two-dimensional. Exact permutation enumeration shows that its only 2-realizer, up to exchanging axes, is

$$\begin{aligned} L_x&=(2,3,0,6,1,4,5),\\ L_y&=(4,0,1,2,5,6,3). \end{aligned}$$

There is also a short hand proof of uniqueness. Since $0$ and $2$ are incomparable, exchange the axes if needed so that $2<_{L_x}0$, hence $0<_{L_y}2$. Common comparabilities and reversal of every incomparable pair then force

$$\begin{gathered} 2<_{L_x}1,\quad3<_{L_x}0,\quad3<_{L_x}5,\quad 3<_{L_x}6,\quad3<_{L_x}1,\quad6<_{L_x}1,\\ 6<_{L_x}5,\quad3<_{L_x}4,\quad6<_{L_x}4,\quad 0<_{L_x}4,\quad2<_{L_x}4,\quad1<_{L_x}4. \end{gathered}$$

For example, $2<_{L_x}0<_{L_x}1$ forces $1<_{L_y}2<_{L_y}6$, hence $6<_{L_x}1$; and $6<_{L_x}5$ forces $4<_{L_y}5<_{L_y}6$, hence $6<_{L_x}4$. These comparisons give the displayed $L_x$, and all incomparable pairs reverse to give the displayed $L_y$.

Let $A_0,\ldots,A_5>0$ be the gaps along $L_x$ and $B_0,\ldots,B_5>0$ those along $L_y$. Three necessary arrival inequalities are

$$\begin{aligned} s_2-s_1&=-A_0-A_1-A_2-A_3+B_2\ge0,\\ s_4-s_3&=A_1+A_2+A_3+A_4 -(B_0+B_1+B_2+B_3+B_4+B_5)\ge0,\\ s_6-s_5&=-A_3-A_4-A_5+B_4\ge0. \end{aligned}$$

Adding them gives the exact Farkas-style certificate

$$-(A_0+A_3+A_5+B_0+B_1+B_3+B_5)\ge0,$$

contradicting positivity. Swapping $L_x,L_y$ is the only other ordered realizer and does not change the argument.

The second obstruction has relation set

$$\{(0,4),(0,6),(1,2),(1,4),(1,5),(1,6),(3,4),(5,6)\}$$

and unique unordered realizer

$$(1,2,5,0,6,3,4)\;/\;(3,0,1,4,5,6,2).$$

Its arrival rows $0\to1,2\to3,4\to5$ sum to

$$-(A_0+A_2+A_5+B_0+B_2+B_4+B_5)\ge0.$$

Six-element audit correction

The reported six-element fixed-realizer certificate is valid only for that realizer. The same poset has the alternate realizer

$$L_1=(0,1,2,4,3,5),\qquad L_2=(3,4,0,5,2,1).$$

The supplied coordinate vectors

$$x=(-9,-8,-1,1,0,2),\qquad y=(-1,5,4,-12,-2,0)$$

increase strictly along $L_1,L_2$, respectively. Their intersections give the same poset as the original realizer. Along arrival $(3,0,1,4,5,2)$, the diagonal sums are

$$(-11,-10,-3,-2,2,3),$$

which are strictly increasing.

Safe replacement wording

The six-element calculation obstructs monotone respacing of one displayed realizer, but it is not a poset-level timing obstruction: the same presented poset has another 2-realizer whose coordinate sums strictly follow arrival. A genuine poset-level obstruction occurs on seven elements. For the up-growing presentation above, exact enumeration leaves one realizer up to exchanging axes, and three required arrival inequalities sum to a negative sum of positive coordinate gaps. Hence no 2D dominance embedding of that presentation can have nondecreasing diagonal coordinate sum. An exhaustive rational census proves that seven is minimal by number of elements; among the 91,206 naturally labeled 2D presentations on seven elements, exactly two dual labeled presentations fail.

This finite obstruction establishes that arbitrary represented up-growing 2D presentations cannot always be compiled with presentation order equal to physical service-time order. It does not prove that the exact quadratic online chain-partition lower bound survives service-time revelation, does not identify the real-time optimum, and does not settle widths below four.