Pattern posets: enumerative, algebraic and algorithmic issues

Cycle 33th Oral Defence of the Phd Thesis
22 marzo 2021
March 22, 2021
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

Venue: The event will take place online through the ZOOM platform. To get the access codes please contact the secretary office (phd.maths [at] unitn.it)
Time: 3.30 p.m.

Matteo Cervetti - PhD in Mathematics, University of Trento

Abstract:
The study of patterns in combinatorial structures has grown up in the past few decades to one of the most active trends of research in combinatorics. Historically, the study of permutations which are constrained by not containing subsequences ordered in various prescribed ways has been motivated by the problem of sorting permutations with certain devices. However, the richness of this notion became especially evident from its plentiful appearances in several very different disciplines, such as pure mathematics, mathematical physics, computer science, biology, and many others. In the last decades, similar notions of patterns have been considered on discrete structures other than permutations, such as integer sequences, lattice paths, graphs, matchings and set partitions. In the first part of this talk I will introduce the general framework of pattern posets and some classical problems about patterns. In the second part of this talk I will present some enumerative results obtained in my PhD thesis about patterns in permutations, lattice paths and matchings. In particular I will describe a generating tree with a single label for permutations avoiding the vincular pattern 1 - 32 - 4, a finite automata approach to enumerate lattice excursions avoiding a single pattern and some results about matchings avoiding juxtapositions and liftings of patterns.

Supervisors: Luca Ferrari - Willem Adriaan De Graaf

Download 
application/pdfCervetti Matteo _prova finale_22 marzo 2021_ore 15.30(PDF | 581 KB)