The distribution of the length of the longest path in random acyclic orientations of a complete bipartite graph

Jessica Khera, Erik Lundberg

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 proba…