skip to main content

Asymptotic enumeration of non-crossing partitions on surfaces.(Report)

Rue, Juanjo ; Sau, Ignasi ; Thilikos, Dimitrios M.

Discrete Mathematics, March 6, 2013, Vol.313(5), p.635(15) [Periódico revisado por pares]

Texto completo disponível

Ver todas as versões
Citações Citado por
  • Título:
    Asymptotic enumeration of non-crossing partitions on surfaces.(Report)
  • Autor: Rue, Juanjo ; Sau, Ignasi ; Thilikos, Dimitrios M.
  • Assuntos: Mathematics
  • É parte de: Discrete Mathematics, March 6, 2013, Vol.313(5), p.635(15)
  • Descrição: To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.disc.2012.12.011 Byline: Juanjo Rue, Ignasi Sau, Dimitrios M. Thilikos Abstract: We generalize the notion of non-crossing partition on a disk to general surfaces with boundary. For this, we consider a surface [SIGMA] and introduce the number C.sub.[SIGMA](n) of non-crossing partitions of a set of n points lying on the boundary of [SIGMA]. Our main result is an asymptotic estimate for C.sub.[SIGMA](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.sub.[SIGMA](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 [SIGMA] is a disk to general surfaces with boundary. Article History: Received 14 May 2012; Revised 4 October 2012; Accepted 11 December 2012 Article Note: (footnote) [star] Most of the results of this paper were announced in the extended abstract "Dynamic programming for graphs on surfaces. Proc. of ICALP'2010, volume 6198 of LNCS, pages 372-383", which is a combination of an algorithmic framework (whose full version can be found in [16]) and the enumerative results presented in this paper.
  • Idioma: English

Buscando em bases de dados remotas. Favor aguardar.