Letter graphs and geometric grid classes of permutations

Alecu, Bogdan, Ferguson, Robert, Kanté, Mamadou Moustapha, Lozin, Vadim, Vatter, Vincent and Zamaraev, Viktor ORCID: 0000-0001-5755-4141 (2021) Letter graphs and geometric grid classes of permutations. [Preprint]

Text 2107.03447v1.pdf - Submitted version Download (376kB) | Preview

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:	Preprint
Uncontrolled Keywords:	math.CO, math.CO
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	15 Jul 2021 08:13
Last Modified:	15 Mar 2024 16:20
DOI:	10.48550/arxiv.2107.03447
Related URLs:	Author
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3130005