From order one catalytic decompositions to context-free specifications: the rewiring bijection
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912589921910784 |
|---|---|
| author | Duchi, Enrica Schaeffer, Gilles |
| author_facet | Duchi, Enrica Schaeffer, Gilles |
| contents | A celebrated result of Bousquet-Mélou and Jehanne states that the bivariate power series solutions of so-called combinatorial polynomial equations with one catalytic variable, also known as catalytic equations, are algebraic series. We give a purely combinatorial derivation of this result in the case of order one catalytic equations (those involving only one univariate unknown series). In particular our approach provides a tool to produce context-free specifications, or bijections with simple multi-type families of trees, for the derivation trees of combinatorial structures that are directly governed by an order one catalytic decomposition.
This provides a simple unified framework to deal with various combinatorial interpretation problems that were solved or raised over the last 50 years since the first such catalytic equation was written by W. T. Tutte in the late 60's to enumerate rooted planar maps. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_20628 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | From order one catalytic decompositions to context-free specifications: the rewiring bijection Duchi, Enrica Schaeffer, Gilles Combinatorics 05A15, 05A19 A celebrated result of Bousquet-Mélou and Jehanne states that the bivariate power series solutions of so-called combinatorial polynomial equations with one catalytic variable, also known as catalytic equations, are algebraic series. We give a purely combinatorial derivation of this result in the case of order one catalytic equations (those involving only one univariate unknown series). In particular our approach provides a tool to produce context-free specifications, or bijections with simple multi-type families of trees, for the derivation trees of combinatorial structures that are directly governed by an order one catalytic decomposition. This provides a simple unified framework to deal with various combinatorial interpretation problems that were solved or raised over the last 50 years since the first such catalytic equation was written by W. T. Tutte in the late 60's to enumerate rooted planar maps. |
| title | From order one catalytic decompositions to context-free specifications: the rewiring bijection |
| topic | Combinatorics 05A15, 05A19 |
| url | https://arxiv.org/abs/2412.20628 |