GATE CS 2024 Set 2 Q24 — Partial Orders and Lattices

A total order containing the partial order $P$ is a linear extension (or topological sort) of the poset defined by $P$.

The non-trivial relations in $P$ (excluding self-loops) are:

• $1 < 2$
• $3 < 2$
• $3 < 4$

We can find the number of valid topological sorts by considering the possible starting elements. The elements with no incoming relations (in-degree 0) are $1$ and $3$.

1. Case 1: The topological sort starts with $1$
   The remaining elements are $\{2, 3, 4\}$ with relations $3 < 2$ and $3 < 4$. Since $3$ must precede both $2$ and $4$, the next element must be $3$. The remaining elements $\{2, 4\}$ have no relations between them and can be ordered in $2! = 2$ ways:
   • $1, 3, 2, 4$
   • $1, 3, 4, 2$
2. Case 2: The topological sort starts with $3$
   The remaining elements are $\{1, 2, 4\}$ with the relation $1 < 2$. The elements with in-degree 0 are now $1$ and $4$:
   • If the next element is $1$, the remaining elements $\{2, 4\}$ have no relations and can be ordered in $2$ ways:
     $(3, 1, 2, 4)$ and $(3, 1, 4, 2)$.
   • If the next element is $4$, the remaining elements $\{1, 2\}$ must be ordered as $1, 2$ due to the relation $1 < 2$:
     $(3, 4, 1, 2)$.

Summing all the cases, the total number of valid total orders is $2 + 2 + 1 = 5$.