# On Finding Two Posets that Cover Given Linear Orders
## 3 Theoretical Bases  
Before we discuss the algorithms, we present the following lemmas and theorems that serve as bases in devising the algorithms. Given posets \(P_{1}=(V,<_{P_{1}})\) and \(P_{2}=(V,<_{P_{2}})\), if \(<_{P_{1}}\subseteq<_{P_{2}}\), then \(\mathcal{L}(P_{2})\subseteq\mathcal{L}(P_{1})\). Proof. : Let the linear order \(L\) be a linear extension of \(P_{2}\), i.e., \(L\in\mathcal{L}(P_{2})\). By definition of linear extension, \(<_{P_{2}}\subseteq<_{L}\). Since \(<_{P_{1}}\subseteq<_{P_{2}}\), then by transitivity, \(<_{P_{1}}\subseteq<_{L}\). This implies that \(L\in\mathcal{L}(P_{1})\). Hence, \(\mathcal{L}(P_{2})\subseteq\mathcal{L}(P_{1})\). Given a pair that is incomparable in \(P\), say \(a\parallel_{P}b\), we know that there are some linear extensions where \(a<b\) while \(b<a\) in the remaining ones. In other words, we can partition Y into \(\text{Y}_{1}=\{L\in\mathcal{L}(P)|a<_{L}b\}\) and \(\text{Y}_{2}=\{L\in\mathcal{L}(P)|b<_{L}a\}\). The next theorem shows that there exists posets \(P_{1}=(V,<_{P_{1}})\), \(P_{2}=(V,<_{P_{2}})\) that cover \(\text{Y}_{1}\) and \(\text{Y}_{2}\), respectively. Moreover, we can derive the relationship of \(<_{P_{1}}\) and \(<_{P_{2}}\) from \(<_{P}\), which is also given in the following theorem. Consider a poset \(P=(V,<_{P})\) and distinct elements \(a,b\in V\) where \(a||_{P}b\). Let \(\text{Y}_{1}=\{L\in\mathcal{L}(P)|a<_{L}b\}\) and \(\text{Y}_{2}=\{L\in\mathcal{L}(P)|b<_{L}a\}\). Moreover, let  
\[<_{A}=\{(x,y)|x\in\{a\}\cup\text{ancestors}(a,P),y\in\{b\}\cup \text{descendants}(b,P)\} \tag{1}\] \[<_{B}=\{(x,y)|x\in\{b\}\cup\text{ancestors}(b,P),y\in\{a\}\cup \text{descendants}(a,P)\} \tag{2}\]  
Then, there exist posets \(P_{1}=(V,<_{P_{1}})\) and \(P_{2}=(V,<_{P_{2}})\) where \(<_{P_{1}}=<_{P}\cup<_{A}\) and \(<_{P_{2}}=<_{P}\cup<_{B}\) such that \(\mathcal{L}(P_{1})=\text{Y}_{1}\) and \(\mathcal{L}(P_{2})=\text{Y}_{2}\). Moreover, in terms of cover relation,  
\[\prec_{P_{1}}=\{(a,b)\}\cup\prec_{P}\backslash(\{(u,b)\in\prec_{P}|u<_{P}a \}\cup\{(a,v)\in\prec_{P}|b<_{P}v\}) \tag{3}\] \[\prec_{P_{2}}=\{(b,a)\}\cup\prec_{P}\backslash(\{(u,a)\in\prec_{P }|u<_{P}b\}\cup\{(b,v)\in\prec_{P}|a<_{P}v\}). \tag{4}\]  
To illustrate the theorem, consider the posets \(P\), \(P_{1}\) and \(P_{2}\) with Hasse diagrams in Figure 2. Since \(3||_{P}4\), let us take elements 3 and 4 as \(a\) and \(b\) in the theorem, respectively. If we generate \(\mathcal{L}(P)\), we have the following linear extensions. \[(1,2,3,4,5,6) (1,2,4,3,5,6)\] \[(1,2,3,4,6,5) (1,2,4,3,6,5)\] \[(1,2,3,5,4,6) (2,1,4,3,5,6)\] \[(2,1,3,4,5,6) (2,1,4,3,6,5)\] \[(2,1,3,4,6,5) (2,4,1,3,5,6)\] \[<_{B}=\{(x,y)|x\in\{b\}\cup\text{ancestors}(b,P),y\in\{a\}\cup \text{descendants}(a,P)\} \tag{2}\]0  
We can partition \(\mathcal{L}(P)\) into two - \(\text{Y}_{1}=\{L\in\mathcal{L}(P)|3<_{L}4\}\) and \(\text{Y}_{2}=\{L\in\mathcal{L}(P)|4<_{L}3\}\). Clearly, \(\text{Y}_{1}\) contains all the linear extensions in the left column while \(\text{Y}_{2}\) contains those in the right  
\[<_{B}=\{(x,y)|x\in\{b\}\cup\text{ancestors}(b,P),y\in\{a\}\cup \text{descendants}(a,P)\} \tag{2}\]1 Example of Theorem 1. From these cases, we can say that \(<_{P_{1}}\) is transitive. Hence, \(<_{P_{1}}\) is a poset. In a similar way, we can also show that \(<_{P_{2}}\) is a poset. Next, we show that \(\mathcal{L}(P_{1})=\mathrm{Y}_{1}\) by showing that \(\mathcal{L}(P_{1})\subseteq\mathrm{Y}_{1}\) and \(\mathrm{Y}_{1}\subseteq\mathcal{L}(P_{1})\). To prove the first direction, suppose \(L\in\mathcal{L}(P_{1})\). Then \(<_{P_{1}}\subseteq<_{L}\). This implies that \(a<_{L}b\). Since \(<_{P}\subseteq<_{P_{1}}\), then we can also say that \(<_{P}\subseteq<_{L}\). This means, \(L\in\mathcal{L}(P)\). Hence, \(L\in\mathrm{Y}_{1}\). To prove the other direction, suppose \(L\in\mathrm{Y}_{1}\). Then, \(L\in\mathcal{L}(P)\) and \(a<_{L}b\). Now, let \(x<_{P_{1}}y\). It suffices to show that \(x<_{L}y\). This clearly holds if \(x<_{P}y\), since \(L\in\mathcal{L}(P)\).