**Comments by the Editors, April 10, 2000:** This is not the first published example of an infinite antichain of permutations in the
pattern containment ordering. Earlier examples are contained in

- V.R. Pratt: Computing permutations with double-ended queues, parallel stacks and parallel queues, Proc. ACM Symp. Theory of Computing 5 (1973), 268-277.
- R.E. Tarjan: Sorting using networks of queues and stacks, Journal of the ACM 19 (1972), 341-346.
- Richard Laver: Math. Proc. of the Cambr. Philos. Soc. 79 (1976), 1-10.

A second comment is that the antichain in this paper has an additional useful property: the permutations in it all avoid the pattern (123). This means that one can adjoin (123) to this antichain to get an example of such an antichain which contains a permutation of just three letters. Clearly this cannot be done with a permutation of two letters in the antichain, so the construction is best possible in that sense.