The asymptotic number of score sequences
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914159151546368 |
|---|---|
| author | Kolesnik, Brett |
| author_facet | Kolesnik, Brett |
| contents | A tournament on a graph is an orientation of its edges. The score sequence lists the in-degrees in non-decreasing order. Works by Winston and Kleitman (1983) and Kim and Pittel (2000) showed that the number $S_n$ of score sequences on the complete graph $K_n$ satisfies $S_n=Θ(4^n/n^{5/2})$. By combining a recent recurrence relation for $S_n$ in terms of the Erdős--Ginzburg--Ziv numbers $N_n$ with the limit theory for discrete infinitely divisible distributions, we observe that $n^{5/2}S_n/4^n\to e^λ/2\sqrtπ$, where $λ=\sum_{k=1}^\infty N_k/k4^k$. This limit agrees numerically with the asymptotics of $S_n$ conjectured by Takács (1986). We also identify the asymptotic number of strong score sequences, and show that the number of irreducible subscores in a random score sequence converges in distribution to a shifted negative binomial with parameters $r=2$ and $p=e^{-λ}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_13563 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | The asymptotic number of score sequences Kolesnik, Brett Combinatorics Probability 05A16, 05C20, 05C30, 11P21, 51M20, 52B05, 60E07, 60K05 A tournament on a graph is an orientation of its edges. The score sequence lists the in-degrees in non-decreasing order. Works by Winston and Kleitman (1983) and Kim and Pittel (2000) showed that the number $S_n$ of score sequences on the complete graph $K_n$ satisfies $S_n=Θ(4^n/n^{5/2})$. By combining a recent recurrence relation for $S_n$ in terms of the Erdős--Ginzburg--Ziv numbers $N_n$ with the limit theory for discrete infinitely divisible distributions, we observe that $n^{5/2}S_n/4^n\to e^λ/2\sqrtπ$, where $λ=\sum_{k=1}^\infty N_k/k4^k$. This limit agrees numerically with the asymptotics of $S_n$ conjectured by Takács (1986). We also identify the asymptotic number of strong score sequences, and show that the number of irreducible subscores in a random score sequence converges in distribution to a shifted negative binomial with parameters $r=2$ and $p=e^{-λ}$. |
| title | The asymptotic number of score sequences |
| topic | Combinatorics Probability 05A16, 05C20, 05C30, 11P21, 51M20, 52B05, 60E07, 60K05 |
| url | https://arxiv.org/abs/2209.13563 |