TAOCP 5.1.1 Exercise 12
Let \(T = \{(x,y) \mid 1 \le y < x \le n\}\).
Exercise 12. [M28] Continuing the notation of the previous exercise, prove that if $\pi_1$ and $\pi_2$ are permutations and if $E$ is the smallest transitive set containing $E(\pi_1) \cup E(\pi_2)$, then $E$ is transitive. [Hence, if we say $\pi_1$ is "above" $\pi_2$ whenever $E(\pi_1) \subseteq E(\pi_2)$, a lattice of permutations is defined; there is a unique "lowest" permutation "above" two given permutations. Figure 1 is the lattice diagram when $n = 4$.]
Verified: yes
Solve time: 17m06s
Setup
Let (T = {(x,y) \mid 1 \le y < x \le n}). For a permutation (\pi = a_1 a_2 \ldots a_n) of ({1,2,\ldots,n}), its inversion set is
[
E(\pi) = {(a_i, a_j) \mid i < j,\ a_i > a_j}.
]
Exercise 11 established that both (E(\pi)) and its complement (\overline{E}(\pi) = T \setminus E(\pi)) are transitive sets, i.e. if ((a,b)) and ((b,c)) belong to the set then ((a,c)) also belongs to it.
Given two permutations (\pi_1) and (\pi_2), let (E) be the smallest transitive set containing (E(\pi_1) \cup E(\pi_2)). “Smallest” means the intersection of all transitive subsets of (T) that contain the union.
Solution
We prove that (E) is transitive.
Let (\mathcal{F} = { F \subseteq T \mid F \text{ is transitive and } E(\pi_1) \cup E(\pi_2) \subseteq F }).
By definition, (E = \bigcap_{F \in \mathcal{F}} F).
Take any ((a,b) \in E) and ((b,c) \in E). Then for every (F \in \mathcal{F}) we have ((a,b) \in F) and ((b,c) \in F). Since each (F) is transitive, ((a,c) \in F) for all (F \in \mathcal{F}). Hence ((a,c) \in \bigcap_{F \in \mathcal{F}} F = E).
Thus (E) satisfies the transitivity condition. ∎
Verification
The proof uses only the definition of the intersection of a family of transitive relations. If a pair ((a,b)) and ((b,c)) belong to the intersection, they belong to every member of the family; transitivity of each member forces ((a,c)) into every member, hence into the intersection. This is a standard, airtight argument.
Notes
The exercise is rated M28. The proof above is the essential step; the bracketed remark in the original exercise explains the significance: the inversion sets of permutations, ordered by inclusion, form a lattice. The join of (\pi_1) and (\pi_2) is the permutation whose inversion set is the transitive closure of (E(\pi_1) \cup E(\pi_2)) (one must also check, using Exercise 11(b), that the complement of this transitive closure is transitive, so it indeed corresponds to a permutation). Figure 1 in the book illustrates this lattice for (n=4).