A combinatorial link between labelled graphs and increasingly labelled Schröder trees - Sorbonne Université
Conference Papers Year : 2022

A combinatorial link between labelled graphs and increasingly labelled Schröder trees

Antoine Genitrini
Mehdi Naima
  • Function : Author
  • PersonId : 1135455

Abstract

In this paper we study a model of Schröder trees whose labelling is increasing along the branches. Such tree family is useful in the context of phylogenetic. The tree nodes are of arbitrary arity (i.e. out-degree) and the node labels can be repeated throughout different branches of the tree. Once a formal construction of the trees is formalized, we then turn to the enumeration of the trees inspired by a renormalisation due to Stanley on acyclic orientations of graphs. We thus exhibit links between our tree model and labelled graphs and prove a one-to-one correspondence between a subclass of our trees and labelled graphs. As a by-product we obtain a new natural combinatorial interpretation of Stanley’s renormalising factor. We then study different combinatorial characteristics of our tree model and finally, we design an efficient uniform random sampler for our tree model based on the classical recursive generation method.
Fichier principal
Vignette du fichier
paper_soumission_finale.pdf (6.83 Mo) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-03680342 , version 1 (27-05-2022)
hal-03680342 , version 2 (21-08-2022)

Identifiers

Cite

Antoine Genitrini, Mehdi Naima, Olivier Bodini. A combinatorial link between labelled graphs and increasingly labelled Schröder trees. The 15th Latin American Theoretical Informatics Symposium, Nov 2022, Guanajuato, Mexico. pp.493--509, ⟨10.1007/978-3-031-20624-5_30⟩. ⟨hal-03680342v2⟩
201 View
121 Download

Altmetric

Share

More