Hostname: page-component-6bf8c574d5-xtvcr Total loading time: 0 Render date: 2025-02-23T11:04:35.287Z Has data issue: false hasContentIssue false
  • English
  • Français

Permutation classes and polyomino classes with excluded submatrices

Published online by Cambridge University Press:  03 July 2015

DANIELA BATTAGLINO ,
MATHILDE BOUVEL ,
ANDREA FROSINI  and
SIMONE RINALDI
DANIELA BATTAGLINO
Affiliation:
Dipartimento di Ingegneria dell'Informazione e Scienza Matematiche, Via Roma, 56, 53100, Siena, Italy Email: [email protected], [email protected]
MATHILDE BOUVEL
Affiliation:
Institut für Mathematik, Universität Zürich, Winterthurerstrasse 190, CH-8057 Zürich, Switzerland Email: [email protected]
ANDREA FROSINI
Affiliation:
Dipartimento di Matematica e Informatica, viale Morgagni 67, 50134, Firenze, Italy Email: [email protected]
SIMONE RINALDI
Affiliation:
Dipartimento di Ingegneria dell'Informazione e Scienza Matematiche, Via Roma, 56, 53100, Siena, Italy Email: [email protected], [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 27 , Special Issue 2: Special Issue: XIV ICTCS , February 2017 , pp. 157 - 183
Copyright
Copyright © Cambridge University Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Albert, M. (2012). PermLab: Software for permutation patterns, Available at http://www.cs.otago.ac.nz/staffpriv/malbert/permlab.php.Google Scholar
Battaglino, D. (2014). Enumeration of polyominoes defined in terms of pattern avoidance or convexity constraints, Thesis of the University of Siena and the University of Nice Sophia Antipolis, Available at http://arxiv.org/abs/1405.3146.Google Scholar
Baxter, G. (1964). On fixed points of the composite of commuting functions. Proceedings of the American Mathematical Society 15 (6) 851–855.Google Scholar
Bernini, A., Ferrari, L., Pinzani, R. and West, J. (2013). Pattern-avoiding Dyck paths. In: Proceedings of 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), Paris, France, June 24–28, in: DMTCS Proceedings Series, vol. AS, 683–694.CrossRefGoogle Scholar
Björner, A. (1990). The Möbius function of subword order. Invariant Theory and Tableaux (Minneapolis, MN, 1988), IMA, Math. Appl., vol. 19, Springer, New York 118–124.Google Scholar
Bona, M. (2004). Combinatorics of Permutations, Chapman-Hall and CRC Press.Google Scholar
Bousquet-Mélou, M. (1996). A method for the enumeration of various classes of column-convex polygons. Discrete Mathematics 154 1–25.Google Scholar
Bousquet-Mélou, M., Claesson, A., Dukes, M. and Kitaev, S. (2010). (2 + 2)-free posets, ascent sequences and pattern avoiding permutations. Journal of Combinatorial Theory, Series A 117 (7) 884–909.CrossRefGoogle Scholar
Brändén, P. and Claesson, A. (2011). Mesh patterns and the expansion of permutation statistics as sums of permutation patterns. Electronic Journal of Combinatorics 18 (2) P5.Google Scholar
Burstein, A. (1998). Enumeration of Words with Forbidden Patterns, Ph.D. thesis, University of Pennsylvania.Google Scholar
Castiglione, G., Frosini, A., Munarini, E., Restivo, A. and Rinaldi, S. (2007). Combinatorial aspects of L-convex polyominoes. European Journal of Combinatorics 28 1724–1741.CrossRefGoogle Scholar
Castiglione, G., Frosini, A., Restivo, A. and Rinaldi, S. (2005a). A tomographical characterization of L-convex polyominoes. In: Andres, E., Damiand, G., Lienhardt, P. (eds.) Proceedings of Discrete Geometry for Computer Imagery 12th International Conference (DGCI 2005), Poitiers, France, April 11–13. Lecture Notes in Computer Science 3429 115–125.Google Scholar
Castiglione, G., Frosini, A., Restivo, A. and Rinaldi, S. (2005b). Enumeration of L-convex polyominoes by rows and columns. Theoretical Computer Science 347 336–352.CrossRefGoogle Scholar
Castiglione, G. and Restivo, A. (2003). Reconstruction of L-convex Polyominoes. Electronic Notes in Discrete Mathematics 12 290–301.Google Scholar
Castiglione, G. and Restivo, A. (2005). Ordering and convex polyominoes. In: Margenstern, M. (ed.) Proceedings of Machines, Computations, and Universality (MCU 2004), Saint Petersburg, Russia, September 21–24, 2004. Springer Lecture Notes in Computer Science 3354 128–139.CrossRefGoogle Scholar
Dairyko, M., Pudwell, L., Tyner, S. and Wynn, C. (2012). Non-contiguous pattern avoidance in binary trees. Electronic Journal of Combinatorics 19 (3) 22.Google Scholar
Daly, D. and Pudwell, L. (2014). Pattern avoidance in the rook monoid. Journal of Combinatorics 5 (4) 471–497.Google Scholar
Delest, M. P. and Viennot, X. (1984). Algebraic languages and polyominoes enumeration. Theoretical Computer Science 34 169–206.Google Scholar
Gardner, M. (1957). Mathematical games. Scientific American 196 126–134.Google Scholar
Golomb, S. W. (1954). Checkerboards and polyominoes. American Mathematical Monthly 61 (10) 675–682.Google Scholar
Goyt, A. (2008). Avoidance of partitions of a three element set. Advances in Applied Mathematics 41 95–114.CrossRefGoogle Scholar
Guibert, O. (1995). Combinatoire des permutations à motifs exclus en liaison avec mots, cartes planaires et tableaux de Young, Ph.D. thesis, University of Bordeaux.Google Scholar
Klazar, M. (1996). On abab-free and abba-free sets partitions. European Journal of Combinatorics 17 53–68.Google Scholar
Knuth, D. E. (1975). The Art of Computer Programming, 2nd edition, Addison-Wesley Publishing Co., Reading, MA, London, Amsterdam. Vol. 1: Fundamental Algorithms; Addison-Wesley Series in Computer Science and Information Processing.Google Scholar
Marcus, A. and Tardos, G. (July 2004). Excluded permutation matrices and the Stanley-Wilf conjecture. Journal of Combinatorial Theory Series A 107 (1) 153–160.Google Scholar
Rowland, E. (2010). Pattern avoidance in binary trees. Journal of Combinatorial Theory Series A 117 741–758.CrossRefGoogle Scholar
Ryser, H. (1963). Combinatorial mathematics. The Carus Mathematical Monographs, no. 14, The Mathematical Association of America, Rahway.CrossRefGoogle Scholar
Sagan, B. E. (2010). Pattern avoidance in set partitions. Ars Combinatoria 94 79–96.Google Scholar
Simion, R. and Schmidt, F. W. (1985). Restricted permutations. European Journal of Combinatorics 6 383–406.Google Scholar
Steingrìmsson, E. and Tenner, B. E. (2010). The Möbius function of the permutation pattern poset. Journal of Combinatorics 1 39–52.CrossRefGoogle Scholar
Úlfarsson, H. (2011). A unification of permutation patterns related to Schubert varieties. Pure Mathematics and Applications 22 (2) 273–296.Google Scholar