Partially well-ordered closed sets of permutations

MD Atkinson; MM Murphy; Nikola Ruskuc

doi:10.1023/A:1016500300436

Partially well-ordered closed sets of permutations

MD Atkinson, MM Murphy, Nikola Ruskuc

Research output: Contribution to journal › Article › peer-review

Abstract

It is known that the "pattern containment" order on permutations is not a partial well-order. Nevertheless, many naturally defined subsets of permutations are partially well-ordered, in which case they have a strong finite basis property. Several classes are proved to be partially well-ordered under pattern containment. Conversely, a number of new antichains are exhibited that give some insight as to where the boundary between partially well-ordered and not partially well-ordered classes lies.

Original language	English
Pages (from-to)	101-113
Number of pages	13
Journal	Order
Volume	19
Issue number	2
DOIs	https://doi.org/10.1023/A:1016500300436
Publication status	Published - Jun 2002

Keywords

finite basis
involvement
partial well-order
pattern containment
permutation
FORBIDDEN SUBSEQUENCES

Access to Document

10.1023/A:1016500300436

Cite this

@article{b4b6646cf9cb467e85a3f070f52521c9,

title = "Partially well-ordered closed sets of permutations",

abstract = "It is known that the {"}pattern containment{"} order on permutations is not a partial well-order. Nevertheless, many naturally defined subsets of permutations are partially well-ordered, in which case they have a strong finite basis property. Several classes are proved to be partially well-ordered under pattern containment. Conversely, a number of new antichains are exhibited that give some insight as to where the boundary between partially well-ordered and not partially well-ordered classes lies.",

keywords = "finite basis, involvement, partial well-order, pattern containment, permutation, FORBIDDEN SUBSEQUENCES",

author = "MD Atkinson and MM Murphy and Nikola Ruskuc",

year = "2002",

month = jun,

doi = "10.1023/A:1016500300436",

language = "English",

volume = "19",

pages = "101--113",

journal = "Order",

issn = "0167-8094",

publisher = "Springer",

number = "2",

}

TY - JOUR

T1 - Partially well-ordered closed sets of permutations

AU - Atkinson, MD

AU - Murphy, MM

AU - Ruskuc, Nikola

PY - 2002/6

Y1 - 2002/6

N2 - It is known that the "pattern containment" order on permutations is not a partial well-order. Nevertheless, many naturally defined subsets of permutations are partially well-ordered, in which case they have a strong finite basis property. Several classes are proved to be partially well-ordered under pattern containment. Conversely, a number of new antichains are exhibited that give some insight as to where the boundary between partially well-ordered and not partially well-ordered classes lies.

AB - It is known that the "pattern containment" order on permutations is not a partial well-order. Nevertheless, many naturally defined subsets of permutations are partially well-ordered, in which case they have a strong finite basis property. Several classes are proved to be partially well-ordered under pattern containment. Conversely, a number of new antichains are exhibited that give some insight as to where the boundary between partially well-ordered and not partially well-ordered classes lies.

KW - finite basis

KW - involvement

KW - partial well-order

KW - pattern containment

KW - permutation

KW - FORBIDDEN SUBSEQUENCES

UR - http://www.scopus.com/inward/record.url?scp=0141465276&partnerID=8YFLogxK

U2 - 10.1023/A:1016500300436

DO - 10.1023/A:1016500300436

M3 - Article

SN - 0167-8094

VL - 19

SP - 101

EP - 113

JO - Order

JF - Order

IS - 2

ER -

Partially well-ordered closed sets of permutations

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this