# On Finding Two Posets that Cover Given Linear Orders
## 3 Theoretical Bases
Otherwise, \(x<_{A}y\), which implies that (\(x=a\) or \(x<_{P}a\)) and (\(b=y\) or \(b<_{P}y\)), whence (\(x=a\) or \(x<_{L}a\)) and (\(b=y\) or \(b<_{L}y\)). In any case, since \(a<_{L}b\), we get \(x<_{L}y\) by transitivity. In a similar way, it can also be shown that \(\mathcal{L}(P_{2})=\mathrm{Y}_{2}\). Now, let us determine the cover relation \(\prec_{P_{1}}\subseteq<_{P_{1}}\). We first determine which pairs \((x,y)\in<_{A}\) are cover pairs in \(P_{1}\). If \((x,y)=(a,b)\), we know that by definition of \(<_{A}\), there exists no \(w\in V\) such that \((a,w)\in<_{A}\) and \((w,b)\in<_{A}\), otherwise \(a<_{P}b\). Since \(a\parallel_{P}b\), then we also know that there exists no \(w\in V\) such that \((a,w)\in<_{A}\) and \((w,b)\in<_{A}\). Hence, \((a,b)\in<_{P_{1}}\). On the other hand, any other value of \((x,y)\) in \(<_{A}\) will lead to (\(x<_{P_{1}}a<_{P_{1}}b<_{P_{1}}y\)), (\(x=a<_{P_{1}}b<_{P_{1}}y\)) or (\(x<_{P_{1}}a<_{P_{1}}b=y\)), which all imply that \((x,y)\
otin\prec_{P_{1}}\). Hence, the only pair in \(<_{A}\) that is covered in \(P_{1}\) is \((a,b)\). Now, we know that \(<_{P}\) corresponds to \(\prec_{P}\). Hence, \(\prec_{P_{1}}\) is the transitive reduction of \(\{(a,b)\}\cup\prec_{P}\). To get the transitive reduction, we have to elimate pairs in \(\prec_{P}\) that are not in \(\prec_{P_{1}}\) because the addition of \((a,b)\) no longer makes them covered. These are the following:  
* \(u\prec_{P}b\) where \(u<_{P}a\) In this case \(u<_{P_{1}}a<_{P_{1}}b\), hence, \((u,b)\
otin\prec_{P_{1}}\). * \((a\prec_{P}v)\) where \(b<_{P}v\) In this case \(a<_{P_{1}}b<_{P_{1}}v\), hence, \((a,v)\
otin\prec_{P_{1}}\)  
Hence, \(\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\}\}\). In a similar way, we can derive the formula for \(\prec_{P_{2}}\). **Corollary 1**. : _If the poset \(P=(V,<_{P})\) in Theorem 1 is a tree-poset, then Equations (3) and (4) become Equations (5) and (6), respectively._  
\[\prec_{P_{1}}= \begin{cases}\{(a,b)\}\cup\prec_{P},&\text{if \ parent}(b,P)\ \ ||_{P}\ a\\ \{(a,b)\}\cup\prec_{P}\backslash\{(parent(b,P),b)\},&\text{if \ parent}(b,P)\ <_{P}\ a \end{cases}  \tag{5}\]  
\[\prec_{P_{2}}= \begin{cases}\{(b,a)\}\cup\prec_{P},&\text{if \ parent}(a,P)\ \ ||_{P}\ b\\ \{(b,a)\}\cup\prec_{P}\backslash\{(parent(a,P),a)\},&\text{if \ parent}(a,P)\ \ <_{P}\ b \end{cases}  \tag{6}\]  
Proof. : From Theorem 1, \(\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\})\). First, we show that \(\{(a,v)\in\prec_{P}|b<_{P}v\}=\emptyset\) if \(P\) is a tree-poset. Suppose there exists such \(v\) where \(a\prec_{P}v\) and \(b<_{P}v\). Since, every non-root node in a tree-poset is covered by only one element, then only \(a\) covers \(v\). Then it must be that \(b<_{P}a\), so that \(b<_{P}v\). This is a contradiction to the assumption that \(a||pb\). Hence, \(\{(a,v)\in\prec_{P}|b<_{P}v\}=\emptyset\). Next, we examine the set \(\{(u,b)\in\prec_{P}|u<_{P}a\}\). If \(P\) is a tree-poset, then there exists only one possible \(u\) that covers \(b\), which is \(parent(b,P)\). Hence, we have two possibilities. If \(parent(b,P)<_{P}a\) then \(\prec_{P_{1}}=\{(a,b)\}\cup\prec_{P}\backslash\{(parent(b,P),b)\}\). Note that \(a\
ot<_{P}parent(b,P)\), otherwise \(a<_{P}b\). Hence, the only other condition is when \(parent(b,P)||_{Pu}\). With this condition, Equation (3) then becomes \(\prec_{P_{1}}=\prec_{P}\cup\{((a,b)\}\). We can prove Equation (6) in a similar way.