LisMath Seminar 

26/06/2018, 16:00 — 16:30 — Room 6.2.33, Faculty of Sciences of the Universidade de Lisboa
Fábio Silva, LisMath, Faculdade de Ciências, Universidade de Lisboa

Patience Sorting monoids and their combinatorics

Monoids arising from combinatorial objects have been intensively studied in recent years. Important examples include the plactic, the sylvester, the Chinese, the hypoplactic, the Baxter, and the stalactic monoids, which are, respectively, associated to the following combinatorial objects: Young tableaux, binary trees, Chinese staircases, quasi-ribbon tableaux, pairs of twin binary trees, and stalactic tableaux.

In this talk we present two monoids which arise in a similar way, the left Patience Porting monoid (lPS monoid), also known in the literature as the Bell monoid, and the right Patient Sorting monoid (rPS monoid), that are, respectively, associated to lPS tableaux and rPS tableaux.

Several properties regarding the monoids mentioned in the first paragraph have been considered. Naturally, we pose the same kind of questions for the lPS and rPS monoids. In this seminar, we will discuss some of our results, which include:

• presentations, growth, identities and automacity regarding both monoids;
• Robinson-Schensted-Knuth-type correspondences for the two types of tableaux;
• formulas to count both the number of each type of tableaux for given evaluations, as well as the Bell numbers, together with a hook length formula;
• the cyclic shift graph of the finitely ranked rPS monoids and the diameter of their connected components.