v7i1n2 — Comment 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

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

Our thanks go to Drs. Michael Atkinson and Martin Klazar for bringing these papers to our attention.

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.