The distribution of the length of the longest path in random acyclic orientations of a complete bipartite graph
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_ | 1866909294027341824 |
|---|---|
| author | Khera, Jessica Lundberg, Erik |
| author_facet | Khera, Jessica Lundberg, Erik |
| contents | Randomly sampling an acyclic orientation on the complete bipartite graph $K_{n,k}$ with parts of size $n$ and $k$, we investigate the length of the longest path. We provide a probability generating function for the distribution of the longest path length, and we use Analytic Combinatorics to perform asymptotic analysis of the probability distribution in the case of equal part sizes $n = k$ tending toward infinity. We show that the distribution is asymptotically Gaussian, and we obtain precise asymptotics for the mean and variance. These results address a question asked by Peter J. Cameron.
Keywords: bipartite graph, directed graph, random graph, acyclic orientation, poly-Bernoulli numbers, lonesum matrices, generating function, analytic combinatorics, asymptotics. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_12716 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The distribution of the length of the longest path in random acyclic orientations of a complete bipartite graph Khera, Jessica Lundberg, Erik Combinatorics Complex Variables Probability 05A16, 05C20, 05C30, 60C05 Randomly sampling an acyclic orientation on the complete bipartite graph $K_{n,k}$ with parts of size $n$ and $k$, we investigate the length of the longest path. We provide a probability generating function for the distribution of the longest path length, and we use Analytic Combinatorics to perform asymptotic analysis of the probability distribution in the case of equal part sizes $n = k$ tending toward infinity. We show that the distribution is asymptotically Gaussian, and we obtain precise asymptotics for the mean and variance. These results address a question asked by Peter J. Cameron. Keywords: bipartite graph, directed graph, random graph, acyclic orientation, poly-Bernoulli numbers, lonesum matrices, generating function, analytic combinatorics, asymptotics. |
| title | The distribution of the length of the longest path in random acyclic orientations of a complete bipartite graph |
| topic | Combinatorics Complex Variables Probability 05A16, 05C20, 05C30, 60C05 |
| url | https://arxiv.org/abs/2408.12716 |