Bijections between planar maps and planar linear normal $λ$-terms with connectivity condition
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911256355536896 |
|---|---|
| author | Fang, Wenjie |
| author_facet | Fang, Wenjie |
| contents | The enumeration of linear $λ$-terms has attracted quite some attention recently, partly due to their link to combinatorial maps. Zeilberger and Giorgetti (2015) gave a recursive bijection between planar linear normal $λ$-terms and planar maps, which, when restricted to 2-connected $λ$-terms (i.e., without closed sub-terms), leads to bridgeless planar maps. Inspired by this restriction, Zeilberger and Reed (2019) conjectured that 3-connected planar linear normal $λ$-terms have the same counting formula as bipartite planar maps. In this article, we settle this conjecture by giving a direct bijection between these two families. Furthermore, using a similar approach, we give a direct bijection between planar linear normal $λ$-terms and planar maps, whose restriction to 2-connected $λ$-terms leads to loopless planar maps. This bijection seems different from that of Zeilberger and Giorgetti, even after taking the map dual. We also explore enumerative consequences of our bijections. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2202_03542 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Bijections between planar maps and planar linear normal $λ$-terms with connectivity condition Fang, Wenjie Combinatorics Logic in Computer Science The enumeration of linear $λ$-terms has attracted quite some attention recently, partly due to their link to combinatorial maps. Zeilberger and Giorgetti (2015) gave a recursive bijection between planar linear normal $λ$-terms and planar maps, which, when restricted to 2-connected $λ$-terms (i.e., without closed sub-terms), leads to bridgeless planar maps. Inspired by this restriction, Zeilberger and Reed (2019) conjectured that 3-connected planar linear normal $λ$-terms have the same counting formula as bipartite planar maps. In this article, we settle this conjecture by giving a direct bijection between these two families. Furthermore, using a similar approach, we give a direct bijection between planar linear normal $λ$-terms and planar maps, whose restriction to 2-connected $λ$-terms leads to loopless planar maps. This bijection seems different from that of Zeilberger and Giorgetti, even after taking the map dual. We also explore enumerative consequences of our bijections. |
| title | Bijections between planar maps and planar linear normal $λ$-terms with connectivity condition |
| topic | Combinatorics Logic in Computer Science |
| url | https://arxiv.org/abs/2202.03542 |