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.


Full Text: PDF COMMENT