Identities and bases in plactic, hypoplactic, sylvester, and related monoids

Research output: ThesisDoctoral Thesis

Abstract

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 active research topic is the identities satisfied by the plactic monoids of finite rank. It is known that there is no “global" identity satisfied by the plactic monoid of every rank. In contrast, monoids related to the plactic monoid, such as the hypoplactic monoid (the monoid of quasi-ribbon tableaux), sylvester monoid (the monoid of binary search trees) and Baxter monoid (the monoid of pairs of twin binary search trees), satisfy global identities, and the shortest identities have been characterized. In this thesis, we present new results on the identities satisfied by the hypoplactic, sylvester, #-sylvester and Baxter monoids. We show how to embed these monoids, of any rank strictly greater than 2, into a direct product of copies of the corresponding monoid of rank 2. This confirms that all monoids of the same family, of rank greater than or equal to 2, satisfy exactly the same identities. We then give a complete characterization of those identities, thus showing that the identity checking problems of these monoids are in the complexity class P, and prove that the varieties generated by these monoids have finite axiomatic rank, by giving a finite basis for them. We also give a subdirect representation ofmultihomogeneous monoids by finite subdirectly irreducible Rees factor monoids, thus showing that they are residually finite.
Original languageEnglish
QualificationDoctor of Philosophy
Awarding Institution
  • Faculdade de Ciências e Tecnologia (FCT)
Supervisors/Advisors
  • Malheiro, António José Mesquita da Cunha Machado, Advisor
  • Cain, Alan James, Co-advisor
Thesis sponsors
Award date11 Feb 2022
Publisher
Publication statusPublished - Mar 2022

Keywords

  • Hypoplactic monoid
  • Sylvester monoid
  • Baxter monoid
  • variety
  • identities
  • equational basis
  • axiomatic rank

Fingerprint

Dive into the research topics of 'Identities and bases in plactic, hypoplactic, sylvester, and related monoids'. Together they form a unique fingerprint.

Cite this