1
$\begingroup$

Given the Hasse Diagram of a Partially Ordered Relation, is it the case that both the POSET itself and its dual POSET have the same number of topological orderings? I have tried a few examples, and although it does seem to be the case, I need a formal way of proving the same. So please help me with this.

$\endgroup$
  • $\begingroup$ What did you try? Where did you get stuck? It is expected of you to show partial progress, thoughts or the obstacles you have encountered. For example, can you explain one of the nontrivial examples you have tried? It will help draw more better answers faster. This site is a knowledge-sharing place instead of simply a solution rendering service. Have you read the answers to how to ask a good question? $\endgroup$ – John L. Jul 7 '19 at 8:15
  • $\begingroup$ I randomly took Hasse Diagrams from Kenneth Rosen, and then compared the topological orders of the original and its dual, and they came out to be same. The best conclusion I've arrived till now, is that probably each topological order gets reversed in case we observe its dual POSET. Also this is a self made question - so there's no way this is meant for any academic interests, so please don't think about it being a homework question or something similar. This is my first question here, so please help me out - I'll make sure to provide more context from now onwards. $\endgroup$ – Lakshay Kakkar Jul 7 '19 at 9:36
  • $\begingroup$ Note that "given the Hasse Diagram of a Partially Ordered Relation" is equivalent to "given a Partially Ordered Relation". $\endgroup$ – John L. Jul 7 '19 at 23:19
  • 1
    $\begingroup$ Yes very helpful. Sorry for being late, I didn't get time as I was preoccupied with a lot of office work this week. Thanks alot for an awesome answer. :) $\endgroup$ – Lakshay Kakkar Jul 21 '19 at 8:16
0
$\begingroup$

Is it the case that both the poset and its dual poset have the same number of topological orderings?

Yes, you have observed/discovered a fact about partially ordered set (poset). In fact, there is a stronger and more pleasing fact, which is a special case of the duality of order theory.


The dual order of a topological ordering of a poset is a topological order of the dual order of that poset.

Given a poset $p$, let $p^{d}$ be the dual order of $p$. Let $p\rightarrowtail$q mean $q$ is a topological ordering of $p$. Then the above claim can be expressed as

$$ p\rightarrowtail q\ \Leftrightarrow p^d \rightarrowtail q^d$$

Proof: All we need to do is to follow the definitions. Let the underlying set of $p$ be $S$, which is also the underlying set of $q$, $p^d$ and $q^d$. For a poset $p$, we use "$\preceq_p$" to denote the binary relation on of $p$ $S\times S$.

"$\Rightarrow$":

  • Let $s_1,s_2\in S$ such that $s_1\preceq_{p^d} s_2$. Then by the definition of the dual order, $s_2\preceq_{p} s_1$. By the definition of a topological sort, $s_2\preceq_{q} s_1$. By the definition of the dual order, $s_1\preceq_{q^d}s_2$.
  • Since $q$ is a total order, so is $q^d$.

"$\Leftarrow$":

  • Let $s_1,s_2\in S$ such that $s_1\preceq_{p} s_2$. Then by the definition of the dual order, $s_2\preceq_{p^d} s_1$. By the definition of a topological sort, $s_2\preceq_{q^d} s_1$. By the definition of the dual order, $s_1\preceq_{q}s_2$.
  • Since $q^d$ is a total order, so is ${(q^d)}^d=q$.

In fact, the implication "$\Leftarrow$" is the dual of the implication "$\Rightarrow$". Replacing $p$ by $p^d$ and $q$ by $q^d$ in the implication "$\Rightarrow$", we get "$\Leftarrow$".

Q.E.D.


The claim above shows that given a poset $p$, whenever we can construct a topological order $q$ for $p$, we also have $q^d$, a topological order for $q^d$. Hence $q\to q^d$ maps the topological orders of $p$ to the topological orders of $p^d$.

Similarly, whenever we can construct a topological order $r$ for $p^d$, we also have $r^d$, a topological order for ${(p^d)}^d=p$.

The map $q\to q^d$ and $r\to r^d$ are inverse functions to each other. So, each map is, in fact, a one-one correspondence. So the number of topological orderings of $p$ equals the number of the topological orderings of $p^d$.


Be careful that the topological orders of the original poset $p$ and its dual $p^d$ might not be same, although they are dual to each other.

For example, we can check the poset $p=\{a,b,c\}$ with $a\preceq_p b$ and $a\preceq_p c$. All topological orders of $p$ shares the unique least element $a$ but don't share greatest elements. All topological orders of $p^d$ shares the unique greatest element $a$ but don't share least elements.


Exercise. A poset is connected if the directed graph representing the poset is connected. Show that the maximum number of topological orderings of a connected poset of $n$ vertices is $(n-1)!$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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