Posets with large dimension and relatively few critical pairs (Q1319081)

The dimension of a poset \(P\) is the minimum number of linear extensions of that poset whose intersection yields \(P\). It is no larger than the collection of incomparable (parallel) pairs \((x,y)\) with the property that \(u<y\) when \(u<x\) and \(x<v\) whenever \(y<u\). For example, if \(S_ n\) is the poset with vertices \(\{a_ 1,\dots, a_ n, b_ n,\dots,b_ n\}\) and \(x<y\) iff \(x= a_ i\); \(y=b_ j\), \(i\neq j\), then \(\dim S_ n= n= | \text{crit} (S_ n)|= |\{ (a_ i, b_ i)\mid i=1, \dots, n\}|\). Including a graph-theoretical approach, the authors are able to apply results and arguments on chromatic numbers to solve the Characterization Problem: for integers \(t\) and \(m\) with \(3\leq t\leq m\leq t+2\), find the minimum set \(P(t,m)\) so that if \(P\) is a poset with \(\dim P =t\) and \(| \text{crit} (P)| =m\), then \(P\) contains a poset in \(P(t,m)\) as a subposet. The conclusions are as follows: If \(m\leq t+1\), then \(P\) contains (a copy of) \(S_ t\) (Theorem 4.2), if \(m\leq 5\) then \(P\) contains \(S_ 3\), \(C\) (the chevron) or \(C^ d\) (the dual, opposite of \(C\)) (Theorem 4.3), while if \(t\geq 4\), then \(P\) contains \(S_ t\), the dimension product \(S_{t-3} \otimes C\) or \(S_{t-3} \otimes C^ d\). The arguments are illustrative of a method that permits global considerations (dimension, linear extensions, etc.) to be localized (critical pairs) by paying close attention to underlying graph-theoretical (diagrammatical) properties and results leading to characterization by substructure containment or noncontainment (i.e., Kuratowski-type) theorems and for which the authors paired this way are also known. It is noted that this work is on the way to better understanding of a conjecture due to Fishburn connecting dimension of posets with numbers of incomparable and critical pairs whose inner mysteries are not yet clear.