An Infinite Antichain of Permutations

Daniel A. Spielman Department of Mathematics

Massachusetts Institute of Technology Cambridge, MA 02139

       spielman@math.mit.edu

Miklós Bóna Department of Mathematics University of Florida Gainesville FL 32605

                                        bona@math.ufl.edu

Submitted February 28, 2000; Accepted March 2, 2000 AMS Classification numbers: 05A05, 06A07

Abstract

We constructively prove that the partially ordered set of finite permutations ordered by deletion of entries contains an infinite antichain. In other words, there exists an infinite collection of permutations no one of which contains another as a pattern.

1 Introduction

When considering a partially ordered set with infinitely many elements, one should wonder whether it contains an infinite antichain (that is, a subset in which each pair of elements are incomparable). It is well known that all antichains of N^{k} (where (x_{1}, x_{2}, ⋯, x_{k}) ≤ (y_{1}, y_{2}, ⋯, y_{k}) if and only if x_{i} ≤ y_{i} for 1 ≤ i ≤ k ) are finite. (See p. 135 of [1]). Another basic result is that all antichains of the partially ordered set of the finite words of a finite alphabet are finite, where x < y if one can delete some letters from y to get x. (This result is due to Higman and can be found in [1], pp. 106–107).

In this paper we examine this question for the partially ordered set P of finite permutations with the following < relation: if m is less than n, and p_{1} is a permutation of the set {1, 2, ⋯, m} and p_{2} is a permutation of the set {1, 2, ⋯, n}, then p_{1} < p_{2} if and only if we can delete n − m elements from p_{2} so that when we re-name the remaining elements according to their rank, we obtain p_{1}. In the well-known terminology of

pattern-avoidance, this amounts to saying that p_{1} < p_{2} if and only if p_{1} is a pattern of p_{2}. For example, 1 3 2 < 2 4 5 3 1 as we can delete 4 and 1 from the latter to get 2 5 3, which becomes 1 3 2 after re-naming. Another way to view this relation is that p_{1} < p_{2} if there are n − m elements of p_{2} that we can delete so that the i-th smallest of the remaining elements precedes exactly b_{i} elements, where b_{i} is the number of elements preceded by i in p_{1}. In other words, the i-th smallest remaining entry of p_{2} precedes the j-th one if and only if i precedes j in p_{1}. In short, p_{1} < p_{2} if p_{1} is “contained” in p_{2}, that is, there is a subsequence in p_{2} in which any two entries relate to each other as the corresponding entries in p_{1}.

We would like to point out that any answer to this question would be somewhat surprising. If there were no infinite antichains in this partially ordered set, that would be surprising because, unlike the two partially ordered sets we mentioned in the first paragraph, P is defined over an infinite alphabet and the “size” of its elements can be arbitrarily large. On the other hand, if there is an infinite antichain, and we will find one, then it shows that this poset is more complex in this sense than the poset of graphs ordered by the operations of edge contraction and vertex deletion. (That this poset of graphs does not contain an infinite antichain is a famous theorem of Robertson and Seymour [2, 3]). This is surprising too, as graphs are usually much more complex than permutations.

2 The infinite antichain

We are going to construct an infinite antichain, {a_{i}}. The elements of this antichain will be very much alike; in fact, they will be identical at the beginning and at the end. Their middle parts will be very similar, too. These properties will help ensure that no element is contained in another one.

Let a_{1} = 13, 12, 10, 14, 8, 11, 6, 9, 4, 7, 3, 2, 1, 5. We view a_{1} as having three parts: a decreasing sequence of length three at its beginning, a long alternating permutation starting with the maximal element of the permutation and ending with the entry 7 at the fifth position from the right (In this alternating part odd entries have only even neighbors and vice versa. Moreover, the odd entries and the even entries form two decreasing subsequences so that 2i is between 2i + 5 and 2i + 3), and a terminating subsequence 3 2 1 5.

To get a_{i+1} from a_{i}, simply insert two consecutive elements right after the maximum element m of a_{i}, and give them the values (m − 4) and (m − 1). Then make the necessary corrections to the rest of the elements, that is, increment all old entries on the left of m (m included) by two and leave the rest unchanged (see Figure 1).

Thus the structure of any a_{i+1} is very similar to that of a_{i}—only the middle part becomes two entries longer.

Figure 1: The pattern of a_{i}

We claim that the a_{i} form an infinite antichain. Assume by way of contradiction that there are indices i, j so that a_{i} < a_{j}. How could that possibly happen? First, note that the rightmost element of a_{j} must map to the rightmost element of a_{i}, since this is the only element in a_{j} preceded by four elements less than itself. Similarly, the maximal element of a_{j} must map to the maximal element of a_{i}, since, excluding the rightmost element, this is the only element preceded by three smaller elements. This implies that the first four and the last six elements of a_{j} must be mapped to the first four and last six elements of a_{i}, thus none of them can be deleted.

Therefore, when deleting elements of a_{j} in order to get a_{i}, we can only delete elements from the middle part, M_{j}. We have already seen that the maximum element cannot be deleted. Suppose we can delete a set

D of entries from M_{j} so that the remaining pattern is a_{i}. First note that D cannot contain three consecutive elements, otherwise every element before those three elements would be larger than every element after them, and a_{i} cannot be divided in two parts with this property. Similarly, D cannot contain two consecutive elements in which the first is even. Thus D can only consist of separate single elements (elements whose neighbors are not in D) and consecutive pairs in which the first element is odd. Clearly, D cannot contain a separate single element as in that case the middle part of resulting permutation would contain a decreasing 3-subsequnce, but the middle part, M_{i}, of a_{i} does not. On the other hand, if D contained two consecutive elements x and y so that x is odd, then the odd element z on the right of y would not be in D as we cannot have three consecutive elements in D, therefore z would be in the remaining copy of a_{i} and z wouldn’t be preceded by two entries smaller than itself. This is a contradiction as all odd entries of M_{i} have this property.

This shows that D is necessarily empty, thus we cannot delete any elements from a_{j} to obtain some a_{i} where i < j.

We have shown that no two elements in {a_{i}} are comparable, so {a_{i}} is an infinite antichain. So there exists an infinite collection of permutations no one of which contains another as a pattern. ◇

References

[1] M. Lothaire, “Combinatorics on Words” pp. 106-107, Addison-Wesley, 1983

[2] N. Robertson, P.D. Seymour, Graph Minors VIII. A Kuratowski theorem for general surfaces, Journal of Combinatorial Theory, series B, 48, 255-288.

[3] N. Robertson, P.D. Seymour, Graph Minors XX. Wagner’s Conjecture, Journal of Combinatorial Theory, series B, to appear.