TAOCP 5.1.1 Exercise 11

Exercise 11. [M25] If $\pi = a_1 a_2 \ldots a_n$ is a permutation of ${1, 2, \ldots, n}$, let

$$E(\pi) = {(a_i, a_j) \mid i < j,\ a_i > a_j}$$

be the set of its inversions, and let

$$\bar{E}(\pi) = {(a_i, a_j) \mid i > j,\ a_i > a_j}$$

be the non-inversions.

a) Prove that $E(\pi)$ and $\bar{E}(\pi)$ are transitive. (A set $S$ of ordered pairs is called transitive if $(a, b)$ and $(b, c)$ are in $S$, then $(a, c)$ is in $S$.)

b) Conversely, let $E$ be any transitive subset of $T = {(x, y) \mid 1 \le y < x \le n}$ whose complement $\bar{E} = T \setminus E$ is also transitive. Prove that there is a permutation $\pi$ such that $E(\pi) = E$.

Verified: yes
Solve time: 8m54s

Solution

Part (a)

Let $T = {(x,y) \mid 1 \le y < x \le n}$. By definition, $E(\pi) \subseteq T$ and $\bar{E}(\pi) = T \setminus E(\pi)$.

Transitivity of $E(\pi)$. Suppose $(a,b), (b,c) \in E(\pi)$. Then $a > b > c$. In the permutation $\pi$, the element $a$ appears before $b$ and $b$ appears before $c$; hence $a$ appears before $c$. Since $a > c$, we have $(a,c) \in E(\pi)$.

Transitivity of $\bar{E}(\pi)$. Suppose $(a,b), (b,c) \in \bar{E}(\pi)$. Then $a > b > c$. In $\pi$, $a$ appears after $b$ and $b$ appears after $c$; therefore $a$ appears after $c$. Because $a > c$, we obtain $(a,c) \in \bar{E}(\pi)$.

Thus both $E(\pi)$ and $\bar{E}(\pi)$ are transitive.

Part (b)

Let $E \subseteq T$ be a transitive set whose complement $\bar{E} = T \setminus E$ is also transitive. We construct a permutation $\pi$ with $E(\pi) = E$.

Define a binary relation $\prec$ on ${1,2,\dots,n}$ as follows: for distinct $x,y$, [ x \prec y ;\iff; \bigl(x > y \land (x,y) \in E\bigr) ;\lor; \bigl(x < y \land (y,x) \in \bar{E}\bigr). ]

We prove that $\prec$ is a strict total order.

Irreflexivity: Trivial because the definition applies only to distinct elements.
Totality: For any distinct $x,y$, set $u = \max(x,y)$ and $v = \min(x,y)$. Then $(u,v) \in T$. Since $T = E \cup \bar{E}$ and $E \cap \bar{E} = \varnothing$, exactly one of $(u,v) \in E$ or $(u,v) \in \bar{E}$ holds. If $(u,v) \in E$ then $u \prec v$; if $(u,v) \in \bar{E}$ then $v \prec u$. Hence precisely one of $x \prec y$ or $y \prec x$ is true.
Transitivity: Assume $x \prec y$ and $y \prec z$; we must show $x \prec z$. Consider the six possible relative orders of the integers $x,y,z$:
- $x > y > z$: Then $(x,y), (y,z) \in E$. Transitivity of $E$ gives $(x,z) \in E$, so $x \prec z$.
- $z > y > x$: Then $(y,x), (z,y) \in \bar{E}$. Transitivity of $\bar{E}$ gives $(z,x) \in \bar{E}$, so $x \prec z$.
- $x > z > y$: We have $(x,y) \in E$ and $(z,y) \in \bar{E}$. If $(x,z) \in \bar{E}$, then transitivity of $\bar{E}$ with $(z,y) \in \bar{E}$ would force $(x,y) \in \bar{E}$, contradicting $(x,y) \in E$. Hence $(x,z) \in E$, so $x \prec z$.
- $y > z > x$: We have $(y,x) \in \bar{E}$ and $(y,z) \in E$. If $(z,x) \in E$, then transitivity of $E$ with $(y,z) \in E$ would give $(y,x) \in E$, contradicting $(y,x) \in \bar{E}$. Hence $(z,x) \in \bar{E}$, so $x \prec z$.
- $y > x > z$: We have $(y,x) \in \bar{E}$ and $(y,z) \in E$. If $(x,z) \in \bar{E}$, then transitivity of $\bar{E}$ with $(y,x) \in \bar{E}$ would yield $(y,z) \in \bar{E}$, contradicting $(y,z) \in E$. Hence $(x,z) \in E$, so $x \prec z$.
- $z > x > y$: We have $(x,y) \in E$ and $(z,y) \in \bar{E}$. If $(z,x) \in E$, then transitivity of $E$ with $(x,y) \in E$ would give $(z,y) \in E$, contradicting $(z,y) \in \bar{E}$. Hence $(z,x) \in \bar{E}$, so $x \prec z$.

In every case $x \prec z$ holds, so $\prec$ is transitive.

Because $\prec$ is a strict total order, we can arrange the numbers $1,2,\dots,n$ in a sequence $a_1, a_2, \dots, a_n$ such that $a_i \prec a_j \iff i < j$. This sequence is a permutation $\pi$ of ${1,\dots,n}$.

Finally, for any pair $(x,y)$ with $x > y$, we have $(x,y) \in E(\pi)$ iff $x$ appears before $y$ in $\pi$, i.e., $x \prec y$. By the definition of $\prec$, this is equivalent to $(x,y) \in E$. Therefore $E(\pi) = E$, as required.

This completes the proof. ∎