An Infinite Antichain of Permutations

  • Daniel A. Spielman
  • Miklós Bóna

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.

Published
2000-03-02
Article Number
N2