Back to overview

Permutation classes and polyomino classes with excluded submatrices.

Type of publication Peer-reviewed
Publikationsform Original article (peer-reviewed)
Author Daniela Battaglino , Mathilde Bouvel , Andrea Frosini , Simone Rinaldi ,
Project Permutation classes: from structure to combinatorial properties
Show all

Original article (peer-reviewed)

Journal Mathematical Structures in Computer Science
Volume (Issue) 27(2)
Page(s) 157 - 1183
Title of proceedings Mathematical Structures in Computer Science

Open Access


This article introduces an analogue of permutation classes in the context of polyominoes. For both permutation classes and polyomino classes, we present an original way of characterizing them by avoidance constraints (namely, with excluded submatrices) and we discuss how canonical such a description by submatrix-avoidance can be. We provide numerous examples of permutation and polyomino classes which may be defined and studied from the submatrix-avoidance point of view, and conclude with various directions for future research on this topic.