Graphical sequences and plane trees
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908826267025408 |
|---|---|
| author | Bassan, Michal Donderwinkel, Serte Kolesnik, Brett |
| author_facet | Bassan, Michal Donderwinkel, Serte Kolesnik, Brett |
| contents | Balister, the second author, Groenland, Johnston and Scott recently showed that there are asymptotically $C4^n/n^{3/4}$ many unordered sequences that occur as degree sequences of graphs. Combining limit theory for infinitely divisible distributions with a new bijective connection between a class of random walk trajectories and a subset counting formula from additive number theory, we describe $C$ in terms of Walkup's number of rooted plane trees. The bijection is related to an instance of the Lévy-Khintchine formula. Our main result complements a result of Stanley, that ordered graphical sequences are related to quasi-forests. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_05110 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Graphical sequences and plane trees Bassan, Michal Donderwinkel, Serte Kolesnik, Brett Combinatorics Probability 05A15, 05A16, 05A17, 05C30, 11P21, 51M20, 52B05, 60E07, 60G50, 60K05 Balister, the second author, Groenland, Johnston and Scott recently showed that there are asymptotically $C4^n/n^{3/4}$ many unordered sequences that occur as degree sequences of graphs. Combining limit theory for infinitely divisible distributions with a new bijective connection between a class of random walk trajectories and a subset counting formula from additive number theory, we describe $C$ in terms of Walkup's number of rooted plane trees. The bijection is related to an instance of the Lévy-Khintchine formula. Our main result complements a result of Stanley, that ordered graphical sequences are related to quasi-forests. |
| title | Graphical sequences and plane trees |
| topic | Combinatorics Probability 05A15, 05A16, 05A17, 05C30, 11P21, 51M20, 52B05, 60E07, 60G50, 60K05 |
| url | https://arxiv.org/abs/2406.05110 |