The Library
Letter graphs and geometric grid classes of permutations
Tools
Alecu, Bogdan, Ferguson, Robert, Kanté, Mamadou Moustapha, Lozin, Vadim V., Vatter, Vincent and Zamaraev, Viktor (2022) Letter graphs and geometric grid classes of permutations. SIAM Journal on Discrete Mathematics, 36 (4). pp. 2774-2797. doi:10.1137/21M1449646 ISSN 0895-4801.
|
PDF
WRAP-letter-graphs-geometric-grid-classes-permutations-2022.pdf - Published Version - Requires a PDF viewer. Download (637Kb) | Preview |
|
PDF
WRAP-Letter-graphs-geometric-grid-classes-permutations-22.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (444Kb) |
Official URL: https://doi.org/10.1137/21M1449646
Abstract
We uncover a connection between two seemingly unrelated notions: lettericity, from structural graph theory, and geometric griddability, from the world of permutation patterns. Both of these notions capture important structural properties of their respective classes of objects. We prove that these notions are equivalent in the sense that a permutation class is geometrically griddable if and only if the corresponding class of inversion graphs has bounded lettericity.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Alternative Title: | |||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||
Journal or Publication Title: | SIAM Journal on Discrete Mathematics | ||||||||
Publisher: | Society for Industrial and Applied Mathematics | ||||||||
ISSN: | 0895-4801 | ||||||||
Official Date: | December 2022 | ||||||||
Dates: |
|
||||||||
Volume: | 36 | ||||||||
Number: | 4 | ||||||||
Page Range: | pp. 2774-2797 | ||||||||
DOI: | 10.1137/21M1449646 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Reuse Statement (publisher, data, author rights): | First Published in SIAM Journal on Discrete Mathematics in 36 (4). pp. 2774-2797., published by the Society for Industrial and Applied Mathematics (SIAM) | ||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||
Copyright Holders: | Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. | ||||||||
Date of first compliant deposit: | 15 August 2022 | ||||||||
Date of first compliant Open Access: | 16 November 2022 | ||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year