A characterization of \((3+1)\)-free posets (Q5930020)

The poset \(3+1\) is the union of a chain 3 with three elements and a chain \(1\) consisting of one element incomparable with the elements of the chain \(3\). If a poset contains no subposet isomorphic to \(3+1\), it is called \((3+1)\)-free. Such posets are characterized in the paper. Let a poset \(P\) with \(n\) elements and with the ordering \(<_P\) be given. A labelling \(\varphi: P\to\{1,\dots, n\}\) is called natural, if \(x<_Py\) implies \(\varphi(x)< \varphi(y)\) for any \(x\) and \(y\). Then \(i<_Pj\) for \(i\) and \(j\) from \(\{1,\dots, n\}\) means \(x<_Py\), where \(i= \varphi(x)\), \(j= \varphi(y)\). The antiadjacency matrix \(A\) of \(P\) has the elements \(a_{ij}\) such that \(a_{ij}= 0\) for \(i<_Pj\) and \(a_{ij}= 1\) otherwise. The square \(A^2\) is denoted by \(B= [b_{ij}]\) and is called the squared antiadjacency matrix of \(P\). The main result is Theorem 3.1. Let \(P\) be a poset of \(n\) elements. \(P\) is \((3+1)\)-free if and only if it may be naturally labelled so that the square antiadjacency matrix \(B\) satisfies the following two conditions for all integers \(1\leq i\leq j\leq n\) and \(1\leq k\leq\ell\leq n\): (1) \(b_{jk}> b_{i\ell}\), (2) If \(b_{ij}- b_{i\ell}\neq b_{jk}- b_{j\ell}\), then \(b_{i\ell}= 0\) and \(b_{ij}< b_{jk}- b_{j\ell}\).