Nie jesteś zalogowany | zaloguj się

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Aktualności — Wydarzenia

Sem. Algebra


Identities and bases in hypoplactic, sylvester, Baxter and stylic monoids

Prelegent: Duarte Ribeiro

2023-04-13 12:15

The ubiquitous plactic monoid, also known as the monoid of Young tableaux, has deep connections to several areas of mathematics, in particular, to the theory of symmetric functions. An actively-studied problem is the identities satisfied by the plactic monoids of finite  rank, which are known to satisfy non-trivial identities but no “global" identity which is satisfied regardless of rank. In contrast, monoids related to the plactic monoid, such as the hypoplactic monoid (the monoid of quasi-ribbon tableaux, connected with quasisymmetric functions), sylvester monoid (the monoid of binary search trees) and Baxter monoid (the monoid of pairs of twin binary search trees, connected with Baxter permutations), satisfy global identities, and the shortest identities have been characterized. On the other hand, the stylic monoid, a finite J-trivial quotient of the plactic monoid, shows promising connections
to the well-studied problem of Simon’s congruence.

The first part of the talk will focus on results on the hypoplactic monoids and on the sylvester and Baxter monoids, obtained in joint work with Alan Cain and António Malheiro (FCT NOVA). We show how to embed these monoids of rank greater than 2 into a direct product of copies of the corresponding monoid of rank 2. As such, we show that these monoids satisfy exactly the same identities, for which we give a full description. Furthermore, we show that the identity checking problem for these monoids is decidable in polynomial time. Then, we show that the varieties generated by these monoids have finite axiomatic rank, and give finite bases for their equational theories.

In the second part of the talk, we show results on the stylic monoids, obtained in joint work with Thomas Aird (University of Manchester). We give a faithful representation of each stylic monoid (of finite rank) by upper unitriangular tropical matrices, and show that these monoids satisfy the same identities as monoids of said matrices, which have been characterized. Therefore, we show that they generate the pseudovarieties Jn in Simon’s hierarchy of J-trivial monoids, are finitely based if and only if their rank is less than 4, and their identity checking problem is decidable in linearithmic time. We also solve the finite basis problem for the stylic monoids with involution.