Sorting posets problem in graph-theoretic language

Question

Sorry for the basic question. It's clear that I have some trivial misunderstandings on posets. I am more familiar with graphs.

I see that this paper https://www.stat.berkeley.edu/~mossel/publications/POSET_SODA09.pdf is the state of the art on sorting posets. I wanted to ask: what's the goal of sorting posets, in terminology of graphs?

The queries made by the oracle seem to be, as far as I can tell: for two nodes $x$,$y$; check if $x$ is reachable from $y$ or $y$ is reachable from $x$ (or neither). Now I wanted to ask what the final sorted poset "looks like". Two scenarios I have here:

(1) It retrieves the underlying Directed Acyclic Graph (DAG).

(2) It retrieves a DAG, except if there is an edge $a \rightarrow b$ and an edge $b \rightarrow c$, we do not know if there is an edge $a \rightarrow c$.

If it is indeed the former, I wanted to know an example of how this can be retrieved with $n(n-1)/2$ queries of the oracle (simple solution) to know how this could even be done.

Answer 1

well i don't how this is related to oracle but i can tell you the basic definition of a poset in a graphs. first i will lay the proper definition for a poset (partially ordered pair) P=(X,<) where X is a set and < is a pratial order that is an irreflexive antisymetric and transitive binary relation. two elements u and v from X are comparable if either u<v or v<u abd imcomparable otherwise. we can form an acyclic digraph D=D(P) from a poset P=(X,<) by takng X as the set of vertices, (u,v) is an arc of D if and only if u<v. this digraph is transitive where (u,w) is an arc wherever both (u,v) and (v,w) are arcs. I hope this answer can help you in your problem.

Answer 2

The way I think of it, a poset is not just any DAG: it must be transitive, meaning that if $x \succ y$ and $y \succ z$, we must also have $x \succ z$. (In graph-theoretic terms, if we have edges $x \to y$ and $y \to z$, the edges $x \to z$ must also exist.)

So, from this point of view, our queries are all just edge queries: when we compare $x,y$, we determine whether $x \to y$, $y \to x$, or neither edge is present. Our goal is to determine the transitive DAG.

We can do this in $\binom n2$ queries by asking about every pair $\{x,y\}$, but we can hope to use transitivity to skip some of the queries.

---

You might also be thinking about the "reachability poset" of a DAG: we write $x \succ y$ if there is a path from $x$ to $y$. In this setting:

• Our queries are reachability queries: when we compare $x,y$, the oracle tells us if there is a path from $x$ to $y$, from $y$ to $x$, or neither.
• Our goal is to determine the answers to all $\binom n2$ queries. Maybe this is represented by a "reachability matrix" $A$ in which $A_{xy}=1$ if there is a path from $x$ to $y$. This is more like your scenario (2) than like (1).

Here, too, $\binom n2$ queries tell us everything we want, but we can hope to make deductions that shorten the time.