Combinatorics of cyclic shifts in plactic, hypoplactic, sylvester, and related monoids

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)
7 Downloads (Pure)

Abstract

The cyclic shift graph of a monoid is the graph whose vertices are elements of the monoid and whose edges link elements that differ by a cyclic shift. For certain monoids connected with combinatorics, such as the plactic monoid (the monoid of Young tableaux) and the sylvester monoid (the monoid of binary search trees), connected components consist of elements that have the same evaluation (that is, contain the same number of each generating symbol). This paper discusses new results on the diameters of connected components of the cyclic shift graphs of the finite-rank analogues of these monoids, showing that the maximum diameter of a connected component is dependent only on the rank. The proof techniques are explained in the case of the sylvester monoid.

Original languageEnglish
Title of host publicationCombinatorics on Words - 11th International Conference, WORDS 2017, Proceedings
PublisherSpringer-Verlag
Pages190-202
Number of pages13
ISBN (Electronic)978-3-319-66396-8
ISBN (Print)978-3-319-66395-1
DOIs
Publication statusPublished - 2017
Event11th International Conference on Combinatorics on Words, WORDS 2017 - Montreal, Canada
Duration: 11 Sep 201715 Sep 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer-Verlag
Volume10432 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference11th International Conference on Combinatorics on Words, WORDS 2017
CountryCanada
CityMontreal
Period11/09/1715/09/17

Keywords

  • Binary search tree
  • Cocharge
  • Cyclic shift
  • Plactic monoid
  • Sylvester monoid

Fingerprint Dive into the research topics of 'Combinatorics of cyclic shifts in plactic, hypoplactic, sylvester, and related monoids'. Together they form a unique fingerprint.

Cite this