1
$\begingroup$

Given a (finite) poset $(P,\leq)$, we can construct the poset $(\mathcal{D}, \subseteq)$ isomorphic to $P$ simply by letting $\mathcal{D}$ be the collection of all "descendant sets" i.e. $\mathtt{D}(x)=\{y\in P: y\leq x\}$ for each $x\in P$. This is such a straightforward observation that I'm assuming it has been mentioned somewhere – but where? A more interesting question is: are there known connections between the existence of joins in $P$ and properties of $\mathcal{D}$?

To give a little bit more motivation, I've been working with directed acyclic graphs – DAGs – which naturally pop up in connection to (mathematical formalizations of) the study of evolutionary histories of, say, different species. For historical reasons, this history is represented with graphs (the DAGs considered originally were just rooted trees). However, every DAG $G=(V,E)$ can be associated to the poset $P_G=(V,\preceq_G)$, where $u\preceq_G v$ if and only if there is a directed path for $v$ to $u$ in $G$. In principle, no interesting information is lost in this conversion between $G$ and $P_G$ –– the only thing of $G$ that is not recoverable from $P_G$ are so-called shortcut edges $(u,v)$, for which there exists a directed path from $u$ to $v$ that avoids the edge $(u,v)$. In particular, since I often use least common ancestors of the DAGs, the corrsponding posets often have some or all joins well-defined. They are not always join-semilattices (although sometimes). Still, I have a nagging feeling that since I don't have a solid background in poset theory, I'm missing some obvious references and connections that could, in a general sense, be helpful in this line of research.

$\endgroup$
6
  • 4
    $\begingroup$ These are called "principal lower sets," see en.wikipedia.org/wiki/Upper_set. This is a special case of the Yoneda embedding: en.wikipedia.org/wiki/Yoneda_lemma $\endgroup$ Commented Mar 11 at 8:32
  • $\begingroup$ Either your definition of acyclicity is different from mine or in a DAG there can be no shortcut paths the way you define them. So let me ask, by a cycle, do you mean an oriented cycle, a non-oriented cycle, or both? $\endgroup$ Commented Mar 11 at 8:49
  • $\begingroup$ Ah! Stupid typo, should of course be an edge (u,v) where there is a path from u to v. I changed to the correct order. DAGs in the sense of directed graph with no oriented cycle. $\endgroup$ Commented Mar 11 at 12:28
  • 1
    $\begingroup$ "A more interesting question is: are there known connections between the existence of joins in $P$ and properties of $\mathcal{D}$?" -- Because of the trivial isomorphism, any properties of $(P,\le)$ can be trivially restated as properties of $(\mathcal D,\subseteq)$. $\endgroup$ Commented Mar 11 at 15:12
  • $\begingroup$ @QiaochuYuan thanks – principal lower sets is indeed a very good search term to start with! $\endgroup$ Commented Mar 11 at 20:19

0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.