LETTER GRAPHS AND GEOMETRIC GRID CLASSES OF PERMUTATIONS



Alecu, Bogdan, Ferguson, Robert, Kante, Mamadou Moustapha, Lozin, Vadim V, Vatter, Vincent and Zamaraev, Victor ORCID: 0000-0001-5755-4141
(2022) LETTER GRAPHS AND GEOMETRIC GRID CLASSES OF PERMUTATIONS. SIAM JOURNAL ON DISCRETE MATHEMATICS, 36 (4). pp. 2774-2797.

Access the full-text of this item by clicking on the Open Access link.

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: Article
Uncontrolled Keywords: inversion graphs, permutation patterns, well-quasi-order
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 09 Mar 2023 10:28
Last Modified: 27 Nov 2023 21:05
DOI: 10.1137/21M1449646
Open Access URL: https://arxiv.org/pdf/2107.03447.pdf
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3168890