Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Algebraic and combin ...
Conference paper

Algebraic and combinatorial structures on Baxter permutations

Samuele Giraudo ORCID (1)
(1) Laboratoire d'Informatique Gaspard-Monge
Download article
Open on HAL
Imported on
January 31, 2017
Published on
December 31, 2010
Last modified on
March 31, 2025
Volume
DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011)
Proceedings
DOI
10.46298/dmtcs.2919
License
https://about.hal.science/hal-authorisation-v1
Indicators
692
Views
601
Downloads

Algebraic and combinatorial structures on Baxter permutations

Samuele Giraudo ORCID (1)
(1) Laboratoire d'Informatique Gaspard-Monge
Abstract
English
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].
French
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].
Keywords
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • Hopf algebras
  • Robinson-Schensted algorithm
  • quotient monoid
  • Baxter permutations
Cited by

Source: OpenCitations

  • Assimilation and Accommodation

    Lecture notes in intelligent transportation and infrastructure

    Authors : Octavian Iordache

    Journal reference : Volume , 2018, pp. 91-111

    DOI : 10.1007/978-3-030-01243-4_5
  • Generic rectangulations

    arXiv (Cornell University)

    Authors : Nathan Reading ORCID

    Journal reference : Volume 33, 2012, pp. 610-623

    DOI : 10.1016/j.ejc.2011.11.004
  • Enumeration of permutations sorted with two passes through a stack and D_8 symmetries

    Discrete Mathematics & Theoretical Computer Science

    Authors : Mathilde Bouvel, Olivier Guibert

    Journal reference : Volume DMTCS Proceedings vol. AR,..., 2012, pp.

    DOI : 10.46298/dmtcs.3080
  • The Hopf algebra of diagonal rectangulations

    Journal of Combinatorial Theory Series A

    Authors : Shirley Law, Nathan Reading ORCID

    Journal reference : Volume 119, 2011, pp. 788-824

    DOI : 10.1016/j.jcta.2011.09.006
  • Optimal Binary Representation of Mosaic Floorplans and Baxter Permutations

    Lecture notes in computer science

    Authors : Bryan He ORCID

    Journal reference : Volume , 2012, pp. 1-12

    DOI : 10.1007/978-3-642-29700-7_1
  • Algebraic and combinatorial structures on pairs of twin binary trees

    Journal of Algebra

    Authors : Samuele Giraudo ORCID

    Journal reference : Volume 360, 2012, pp. 115-157

    DOI : 10.1016/j.jalgebra.2012.03.020
Preview
Loading PDF preview...