GATE CS 1997 Q6.1 — Partial Orders and Lattices

A total order on a set $S$ that contains a given partial order $\leq$ is also known as a linear extension of that partial order.

The set $S$ contains $n+2$ elements: $S = \{x, a_1, a_2, \ldots, a_n, y\}$. The given partial order constraints are:

• $x \leq a_i$ for all $i \in \{1, 2, \ldots, n\}$
• $a_i \leq y$ for all $i \in \{1, 2, \ldots, n\}$

From these constraints, we can deduce the relative positions of the elements in any compatible total order:

1. Since $x \leq a_i \leq y$ for all $i$, $x$ must be the absolute minimum element and must appear first in the total order.
2. Similarly, $y$ must be the absolute maximum element and must appear last in the total order.
3. The elements $\{a_1, a_2, \ldots, a_n\}$ are mutually incomparable with respect to each other. Therefore, they can be arranged in any arbitrary sequence between $x$ and $y$.

Any valid total order will have the structure:

$$\underbrace{x}_{\text{1st position}} \prec \underbrace{a_{\pi(1)} \prec a_{\pi(2)} \prec \ldots \prec a_{\pi(n)}}_{\text{any permutation of } \{a_1, \ldots, a_n\}} \prec \underbrace{y}_{\text{last position}}$$

The number of ways to permute the $n$ incomparable elements $\{a_1, a_2, \ldots, a_n\}$ is given by $n!$.

Thus, the number of total orders containing the partial order $\leq$ is $n!$.