Enumerative combinatorics of pattern posets

13 febbraio 2020
13 February 2020
Contatti: 
Staff Dipartimento di Matematica

Università degli Studi Trento
38123 Povo (TN)
Tel +39 04 61/281508-1625-1701-3898-1980.
dept.math [at] unitn.it

Luogo: Povo Zero, via Sommarive 14 (Povo) – Seminar Room "-1"
Ore: 15.00

"Doc in Progress" is pleased to introduce you to:

  • Matteo Cervetti - PhD in Mathematics, University of Trento

Abstract

In this talk we will introduce some classical enumerative combinatorics issues about pattern posets, with emphasis on some remarkable cases such as the permutation pattern poset, the lattice paths pattern posets and, especially, the matching pattern poset. A matching of semilength n is a partition of {1,...,2n} in blocks with two elements, i.e., a graph on {1,...,2n} such that every vertex has degree one. In this case, given two matchings σ and τ, we say that σ is a pattern of τ when σ can be obtained from τ by deleting some edges of τ and consistently relabelling its vertices, and we call the resulting poset the matching pattern poset. In this context we will present some enumerative results and open problems about pattern avoidance for small patterns, in particular we will focus on the enumeration of the matchings avoiding the juxtapposition of two patterns, working out explicit enumerative formulas for at least two new classes of matchings avoiding a single pattern (and all their equivalents). Finally, we will also introduce the notion of unlabeled pattern as an equivalece class of usual patterns, i.e., an unlabeled graph, and provide enumerative results for some classes of matchings avoiding an unlabeled pattern of semilength three.

 

Download