Comments on Daniel A. Spielman and Miklós Bóna, An Infinite Antichain of Permutations

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

  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.