Asymptotic enumeration of non-crossing partitions on surfaces

Dimitrios M. Thilikos 1, 2 Ignasi Sau 2 Juanjo Rué 3
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We generalize the notion of non-crossing partition on a disk to general surfaces with boundary. For this, we consider a surface Σ and introduce the number CΣ(n) of non-crossing partitions of a set of n points lying on the boundary of Σ. Our main result is an asymptotic estimate for CΣ(n). The proofs use bijective techniques arising from map enumeration, joint with the symbolic method and singularity analysis on generating functions. An outcome of our results is that the exponential growth of CΣ(n) is the same as the one of the n-th Catalan number, i.e., does not change when we move from the case where Σ is a disk to general surfaces with boundary.
Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00804780
Contributeur : Dimitrios M. Thilikos <>
Soumis le : mardi 26 mars 2013 - 12:18:37
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Lien texte intégral

Identifiants

Collections

Citation

Dimitrios M. Thilikos, Ignasi Sau, Juanjo Rué. Asymptotic enumeration of non-crossing partitions on surfaces. Discrete Mathematics, Elsevier, 2013, pp.635-649. 〈http://www.sciencedirect.com/science/article/pii/S0012365X1200533X〉. 〈10.1016/j.disc.2012.12.011〉. 〈lirmm-00804780〉

Partager

Métriques

Consultations de la notice

161