Delphi.science

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

Source: arxiv.org/abs/2611.19164

Aiden Corcoran, Erik Lundberg, Elisabeth Rodriguez

arXivarxiv/2611.19164Nov 14, 2026math.COscore 0

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.

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.19164
curl -X POST /api/v1/records/arxiv/2611.19164/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.19164/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'