-
The distribution of the length of the longest path in random acyclic orientations of a complete bipartite graph
Authors:
Jessica Khera,
Erik Lundberg
Abstract:
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…
▽ More
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.
△ Less
Submitted 22 August, 2024;
originally announced August 2024.
-
Encoding acyclic orientation of complete multipartite graphs
Authors:
Walter Carballosa,
Jessica Khera,
Francisco Reyes
Abstract:
In this work we study the acyclic orientations of complete multipartite graphs. We obtain an encoding of the acyclic orientations of the complete $p$-partite graph with size of its parts $n:=n_1,n_2,\ldots,n_p$ via a vector with $p$ symbols and length $n_1+n_2+\ldots+n_p$ when the parts are fixed but not the vertices in each part. We also give a recursive way to construct all acyclic orientations…
▽ More
In this work we study the acyclic orientations of complete multipartite graphs. We obtain an encoding of the acyclic orientations of the complete $p$-partite graph with size of its parts $n:=n_1,n_2,\ldots,n_p$ via a vector with $p$ symbols and length $n_1+n_2+\ldots+n_p$ when the parts are fixed but not the vertices in each part. We also give a recursive way to construct all acyclic orientations of a complete multipartite graph, this construction can be done by computer easily in order $\mathcal{O}(n)$. Besides, obtained codification of the acyclic orientations allows us to count the number of non-isomorphic acyclic orientations of the complete multipartite graphs. Furthermore, we obtain a closed formula for non-isomorphic acyclic orientations of the complete multipartite graphs with a directed spanning tree. In addition, we obtain a closed formula for the ordinary generating functions for the number of strings in the alphabet $\{s_1,s_2,\ldots,s_p\}$ with $k_1$ characters $s_1$, $k_2$ characters $s_2$, and so on with $k_p$ characters $s_p$ such that no two consecutive characters are the same. Finally, we obtain a closed formula for the number of acyclic orientation of a complete multipartite graph $K_{n_1,\ldots,n_p}$ with labelled vertices.
△ Less
Submitted 15 March, 2023;
originally announced March 2023.
-
Asymptotic enumeration of lonesum matrices
Authors:
Jessica Khera,
Erik Lundberg,
Stephen Melczer
Abstract:
We provide bivariate asymptotics for the poly-Bernoulli numbers, a combinatorial array that enumerates lonesum matrices, using the methods of Analytic Combinatorics in Several Variables (ACSV). For the diagonal asymptotic (i.e., for the special case of square lonesum matrices) we present an alternative proof based on Parseval's identity. In addition, we provide an application in Algebraic Statisti…
▽ More
We provide bivariate asymptotics for the poly-Bernoulli numbers, a combinatorial array that enumerates lonesum matrices, using the methods of Analytic Combinatorics in Several Variables (ACSV). For the diagonal asymptotic (i.e., for the special case of square lonesum matrices) we present an alternative proof based on Parseval's identity. In addition, we provide an application in Algebraic Statistics on the asymptotic ML-degree of the bivariate multinomial missing data problem, and we strengthen an existing result on asymptotic enumeration of permutations having a specified excedance set.
△ Less
Submitted 6 October, 2020; v1 submitted 18 December, 2019;
originally announced December 2019.
