Algebraic and combinatorial structures on Baxter permutations
International audience We give a new construction of a Hopf subalgebra of the Hopf algebra of Free quasi-symmetric functions whose bases are indexed by objects belonging to the Baxter combinatorial family (\emphi.e. Baxter permutations, pairs of twin binary trees, \emphetc.). This construction relie...
Published in: | Discrete Mathematics & Theoretical Computer Science |
---|---|
Main Author: | |
Other Authors: | , , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2011
|
Subjects: | |
Online Access: | https://inria.hal.science/hal-00790742 https://inria.hal.science/hal-00790742v2/document https://inria.hal.science/hal-00790742v2/file/dmAO0135.pdf https://doi.org/10.46298/dmtcs.2919 |
id |
ftuniveiffel:oai:HAL:hal-00790742v2 |
---|---|
record_format |
openpolar |
spelling |
ftuniveiffel:oai:HAL:hal-00790742v2 2024-06-16T07:41:00+00:00 Algebraic and combinatorial structures on Baxter permutations Giraudo, Samuele Laboratoire d'Informatique Gaspard-Monge (LIGM) École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel Bousquet-Mélou Mireille and Wachs Michelle and Hultman Axel Reykjavik, Iceland 2011 https://inria.hal.science/hal-00790742 https://inria.hal.science/hal-00790742v2/document https://inria.hal.science/hal-00790742v2/file/dmAO0135.pdf https://doi.org/10.46298/dmtcs.2919 en eng HAL CCSD Discrete Mathematics and Theoretical Computer Science info:eu-repo/semantics/altIdentifier/doi/10.46298/dmtcs.2919 hal-00790742 https://inria.hal.science/hal-00790742 https://inria.hal.science/hal-00790742v2/document https://inria.hal.science/hal-00790742v2/file/dmAO0135.pdf doi:10.46298/dmtcs.2919 info:eu-repo/semantics/OpenAccess 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011) https://inria.hal.science/hal-00790742 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. pp.387-398, ⟨10.46298/dmtcs.2919⟩ https://dmtcs.episciences.org/2919 Hopf algebras Robinson-Schensted algorithm quotient monoid Baxter permutations [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] info:eu-repo/semantics/conferenceObject Conference papers 2011 ftuniveiffel https://doi.org/10.46298/dmtcs.2919 2024-05-23T00:13:05Z International audience We give a new construction of a Hopf subalgebra of the Hopf algebra of Free quasi-symmetric functions whose bases are indexed by objects belonging to the Baxter combinatorial family (\emphi.e. Baxter permutations, pairs of twin binary trees, \emphetc.). This construction relies on the definition of the Baxter monoid, analog of the plactic monoid and the sylvester monoid, and on a Robinson-Schensted-like insertion algorithm. The algebraic properties of this Hopf algebra are studied. This Hopf algebra appeared for the first time in the work of Reading [Lattice congruences, fans and Hopf algebras, \textitJournal of Combinatorial Theory Series A, 110:237–273, 2005]. Nous proposons une nouvelle construction d'une sous-algèbre de Hopf de l'algèbre de Hopf des fonctions quasi-symétriques libres dont les bases sont indexées par les objets de la famille combinatoire de Baxter (\emphi.e. permutations de Baxter, couples d'arbres binaires jumeaux, \emphetc.). Cette construction repose sur la définition du mono\"ıde de Baxter, analogue du mono\"ıde plaxique et du mono\"ıde sylvestre, et d'un algorithme d'insertion analogue à l'algorithme de Robinson-Schensted. Les propriétés algébriques de cette algèbre de Hopf sont étudiées. Cette algèbre de Hopf est apparue pour la première fois dans le travail de Reading [Lattice congruences, fans and Hopf algebras, \textitJournal of Combinatorial Theory Series A, 110:237–273, 2005]. Conference Object Iceland HAL Univ-Eiffel (Université Gustave Eiffel) Baxter ENVELOPE(162.533,162.533,-74.367,-74.367) Discrete Mathematics & Theoretical Computer Science DMTCS Proceeding Proceedings |
institution |
Open Polar |
collection |
HAL Univ-Eiffel (Université Gustave Eiffel) |
op_collection_id |
ftuniveiffel |
language |
English |
topic |
Hopf algebras Robinson-Schensted algorithm quotient monoid Baxter permutations [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] |
spellingShingle |
Hopf algebras Robinson-Schensted algorithm quotient monoid Baxter permutations [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] Giraudo, Samuele Algebraic and combinatorial structures on Baxter permutations |
topic_facet |
Hopf algebras Robinson-Schensted algorithm quotient monoid Baxter permutations [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] |
description |
International audience We give a new construction of a Hopf subalgebra of the Hopf algebra of Free quasi-symmetric functions whose bases are indexed by objects belonging to the Baxter combinatorial family (\emphi.e. Baxter permutations, pairs of twin binary trees, \emphetc.). This construction relies on the definition of the Baxter monoid, analog of the plactic monoid and the sylvester monoid, and on a Robinson-Schensted-like insertion algorithm. The algebraic properties of this Hopf algebra are studied. This Hopf algebra appeared for the first time in the work of Reading [Lattice congruences, fans and Hopf algebras, \textitJournal of Combinatorial Theory Series A, 110:237–273, 2005]. Nous proposons une nouvelle construction d'une sous-algèbre de Hopf de l'algèbre de Hopf des fonctions quasi-symétriques libres dont les bases sont indexées par les objets de la famille combinatoire de Baxter (\emphi.e. permutations de Baxter, couples d'arbres binaires jumeaux, \emphetc.). Cette construction repose sur la définition du mono\"ıde de Baxter, analogue du mono\"ıde plaxique et du mono\"ıde sylvestre, et d'un algorithme d'insertion analogue à l'algorithme de Robinson-Schensted. Les propriétés algébriques de cette algèbre de Hopf sont étudiées. Cette algèbre de Hopf est apparue pour la première fois dans le travail de Reading [Lattice congruences, fans and Hopf algebras, \textitJournal of Combinatorial Theory Series A, 110:237–273, 2005]. |
author2 |
Laboratoire d'Informatique Gaspard-Monge (LIGM) École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel Bousquet-Mélou Mireille and Wachs Michelle and Hultman Axel |
format |
Conference Object |
author |
Giraudo, Samuele |
author_facet |
Giraudo, Samuele |
author_sort |
Giraudo, Samuele |
title |
Algebraic and combinatorial structures on Baxter permutations |
title_short |
Algebraic and combinatorial structures on Baxter permutations |
title_full |
Algebraic and combinatorial structures on Baxter permutations |
title_fullStr |
Algebraic and combinatorial structures on Baxter permutations |
title_full_unstemmed |
Algebraic and combinatorial structures on Baxter permutations |
title_sort |
algebraic and combinatorial structures on baxter permutations |
publisher |
HAL CCSD |
publishDate |
2011 |
url |
https://inria.hal.science/hal-00790742 https://inria.hal.science/hal-00790742v2/document https://inria.hal.science/hal-00790742v2/file/dmAO0135.pdf https://doi.org/10.46298/dmtcs.2919 |
op_coverage |
Reykjavik, Iceland |
long_lat |
ENVELOPE(162.533,162.533,-74.367,-74.367) |
geographic |
Baxter |
geographic_facet |
Baxter |
genre |
Iceland |
genre_facet |
Iceland |
op_source |
23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011) https://inria.hal.science/hal-00790742 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. pp.387-398, ⟨10.46298/dmtcs.2919⟩ https://dmtcs.episciences.org/2919 |
op_relation |
info:eu-repo/semantics/altIdentifier/doi/10.46298/dmtcs.2919 hal-00790742 https://inria.hal.science/hal-00790742 https://inria.hal.science/hal-00790742v2/document https://inria.hal.science/hal-00790742v2/file/dmAO0135.pdf doi:10.46298/dmtcs.2919 |
op_rights |
info:eu-repo/semantics/OpenAccess |
op_doi |
https://doi.org/10.46298/dmtcs.2919 |
container_title |
Discrete Mathematics & Theoretical Computer Science |
container_volume |
DMTCS Proceeding |
container_issue |
Proceedings |
_version_ |
1802008062508138496 |