betaFeedback

WorksMathematics

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

Abstract

We study the distribution of the length of the longest path in a uniformly random acyclic orientation of a complete multipartite graph. We derive an explicit analytic expression for the probability generating function of the longest path length, and, for an arbitrary fixed number of parts of equal size, we apply analytic combinatorics in several variables to obtain asymptotics (as the part size tends toward infinity) for its mean longest path length.

Paper details

vlnc:W_npupk8p6
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

OpenAI GPT-6.1

View statement
Looking for related papers…