Let $P$ be a partial order on $X.$ Does the relation $E(P)=$ { $(x,y)\in (X\times X)\setminus P:P$ $\cup$ { $(x,y)$ } is a partial order on $X$ } have a name? If not, what's a good thing to call it?


1 Answer 1


I searched online. Also checked several articles/papers on poset topological sorting and linear extension of poset. No name has been found for that relation.

$E(P)$ can be described as the set of ordered pairs compatible to $P$ or the set of ordered pairs extending $P$ minus $P$.

As the asker noted, if an ordered pair belong to an extension of $P$, it does not belong to $E(P)$ necessarily. For example, let $P$ on $X=\{a,b,c\}$ be defined by $a\prec b$. Then $P$ can be extended by letting $b\prec c$ and $a\prec c$. However, only letting $b\prec c$ does not extend $P$ to a bigger poset since $a\prec c$ would be missing. Hence we cannot describe $E(P)$ as the union of all extensions of $P$ minus $P$.

Some names that might be good for $E(P)$ are "the $P$-extending relation", "the extending relation of $P$", or "the $P$-compatible relation".

Once defined at the start of your post/article, the notation $E(P)$ could be the best name for that set, where $E$ is, as you intended probably, shorthand for extension or extending. For the sake of clarity in references, $\text{Ext}(P)$ might be better ($\text{Extension}(P)$ looks a bit long).

  • $\begingroup$ Your answer is helpful - thank you. "E" was indeed for "extension". Perhaps I should have mentioned this question: mathoverflow.net/questions/418092 The answer shows that for $X$ finite, every extension of $P$ contains at least one pair in $E(P)$ (maybe this holds for any $X$). Naming is discussed briefly in the comments. I am now thinking of possibly calling it the "envelope" of $P$ and using "Env($P$)". $\endgroup$ Dec 5, 2022 at 17:07
  • $\begingroup$ Your description "union of all extensions of $P$ minus $P$" isn't accurate, by the way. $\endgroup$ Dec 5, 2022 at 17:20
  • $\begingroup$ @mathematrucker Not sure what you mean by not accurate. What I mean is $E(P)=\{r\in X\times X\mid \exists Q\ (Q \text{ is a poset that extends }Q) \land (r\in Q)\}\setminus P$. $\endgroup$
    – John L.
    Dec 5, 2022 at 21:56
  • $\begingroup$ The pair $(4,7)$ satisfies your condition for the poset at math.stackexchange.com/questions/3480391 but it's not in $E(P)$ for that poset because, for example, the pair $(2,7)$ is not in the poset. $\endgroup$ Dec 5, 2022 at 22:27
  • $\begingroup$ ...hence $P\cup\{(4,7)\}$ fails to satisfy the transitive property. $\endgroup$ Dec 5, 2022 at 22:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.