k-Pop Stack Sortable Permutations and 2-Avoidance

Elder, M; Goh, YK

k-Pop Stack Sortable Permutations and 2-Avoidance

Elder, M

Goh, YK

Permalink

Publisher:: The Electronic Journal of Combinatorics
Publication Type:: Journal Article
Citation:: The Electronic Journal of Combinatorics, 2021, 28, (1)
Issue Date:: 2021-03-26

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Published VersionAdobe PDF (464.96 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Elder, M https://orcid.org/0000-0002-2438-3945
dc.contributor.author	Goh, YK
dc.date.accessioned	2021-03-30T03:48:09Z
dc.date.available	2021-03-30T03:48:09Z
dc.date.issued	2021-03-26
dc.identifier.citation	The Electronic Journal of Combinatorics, 2021, 28, (1)
dc.identifier.issn	1097-1440
dc.identifier.issn	1077-8926
dc.identifier.uri	http://hdl.handle.net/10453/147652
dc.description.abstract	<jats:p>We consider permutations sortable by $k$ passes through a deterministic pop stack. We show that for any $k\in\mathbb{N}$ the set is characterised by finitely many patterns, answering a question of Claesson and Guðmundsson. Moreover, these sets of patterns are algorithmically constructible. Our characterisation demands a more precise definition than in previous literature of what it means for a permutation to avoid a set of barred and unbarred patterns. We propose a new notion called $2$-avoidance.</jats:p>
dc.language	en
dc.publisher	The Electronic Journal of Combinatorics
dc.relation	http://purl.org/au-research/grants/arc/DP160100486
dc.relation.ispartof	The Electronic Journal of Combinatorics
dc.relation.isbasedon	10.37236/9606
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	0101 Pure Mathematics, 0802 Computation Theory and Mathematics
dc.subject.classification	Computation Theory & Mathematics
dc.title	k-Pop Stack Sortable Permutations and 2-Avoidance
dc.type	Journal Article
utslib.citation.volume	28
utslib.for	0101 Pure Mathematics
utslib.for	0802 Computation Theory and Mathematics
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Science
pubs.organisational-group	/University of Technology Sydney/Faculty of Science/School of Mathematical and Physical Sciences
utslib.copyright.status	open_access	*
dc.date.updated	2021-03-30T03:48:08Z
pubs.issue	1
pubs.publication-status	Published online
pubs.volume	28
utslib.citation.issue	1

Abstract:

We consider permutations sortable by $k$ passes through a deterministic pop stack. We show that for any $k\in\mathbb{N}$ the set is characterised by finitely many patterns, answering a question of Claesson and Guðmundsson. Moreover, these sets of patterns are algorithmically constructible. Our characterisation demands a more precise definition than in previous literature of what it means for a permutation to avoid a set of barred and unbarred patterns. We propose a new notion called $2$-avoidance.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/147652