Utilize este identificador para referenciar este registo: http://hdl.handle.net/10362/75311
Título: Combinatorics of cyclic shifts in plactic, hypoplactic, sylvester, and related monoids
Autor: Cain, Alan J.
Malheiro, António
Palavras-chave: Binary search tree
Cocharge
Cyclic shift
Plactic monoid
Sylvester monoid
Theoretical Computer Science
Computer Science(all)
Data: 2017
Editora: Springer Verlag
Resumo: 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.
Descrição: fellowship (IF/01622/2013/CP1161/CT0001). project PTDC/MHC-FIL/2583/2014.
Peer review: yes
URI: http://www.scopus.com/inward/record.url?scp=85028719995&partnerID=8YFLogxK
DOI: https://doi.org/10.1007/978-3-319-66396-8_18
ISBN: 978-3-319-66395-1
978-3-319-66396-8
ISSN: 0302-9743
Aparece nas colecções:Home collection (FCT)

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
1611.04152.pdf164,19 kBAdobe PDFVer/Abrir


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.