Maximal chains of preorders (Q1239171)

Let \({\mathcal P}_n\) denote the family of all reflexive and transitive binary relations on the set \([n]=\{1,2,\dots,n\}\). With respect to set-inclusion \({\mathcal P}_n\) is a lattice whose smallest element is \(\Delta=\{(x,x) \mid x\in [n]\}\) and whose greatest element is \([n]\times[n]\). Let \(P,Q\in{\mathcal P}_n\) such that \(P\subset Q\). A chain \(\Gamma\) of length \(q\) from \(P\) to \(Q\) is a sequence of \(q+1\) elements of \({\mathcal P}_n\), \(\Gamma=(P_1,P_2,\dots,P_{q+1})\), such that \(P=P_1\), \( P_1\subset P_2\subset\ldots\subset P_{q+1}\), \(P_{q+1}=Q\). (All inclusions are strict). A chain from \(P\) to \(Q\) is maximal if it is not a proper subsequence of another one. For \(n\geq3\), there are in \({\mathcal P}_n\) two maximal chains of different lengths with the same ends. The paper is concerned with maximal chains of maximal length. For \(P\in{\mathcal P}_n\), \(\bar P\) denotes the canonical equivalence relation \(\bar P=\{(x,y)\in [n] \times [n] \mid (y,x)\in P\) and \((x,y)\in P\}\) and \(P/\bar P\) the quotient relation on \([n]/\bar P\). \(P/\bar P\) is a strict ordering. Let \(e(P)\) be the cardinal of \([n]/\bar P\) and \(o(P)\) the number of edges in the graph representing \(P/\bar P\). One has the following results: Theorem. Let \(P\neq Q\) be two elements of \({\mathcal P}_n\) such that \(P\subset Q\). There exists an element of \({\mathcal P}_n\) such that \(P\subset R\subseteq Q\) and either \(e(r) =e(P)\) and \(o(R) =o(P) +1\) or \(e(R) =e(P) - 1\) and \(o(P)-o(R)\leq e(P) -1\). Theorem: Let \(P\in {\mathcal P}_n\). The length of a maximal chain from \(P\) to \([n]\times[n]\) is less than \(q(P)=\frac{e(P)(e(P)-1)}2-o(P)-1\). There exists a chain from \(P\) to \([n] \times [n]\) of length exactly \(q(P)\).