CLT for the Weight of the Minimum Spanning Arborescence on the Complete Directed Graph
Abstract
The minimum spanning arborescence (MSA) with a fixed boundary, defined on weighted directed graphs, is the directed analogue of the minimum spanning tree (MST). The behaviour of the MSA has been of recent interest and is known to be quite different from that of its undirected counterpart. On the complete directed graph, and for edge weights given by i.i.d. random variables with a broad class of distributions, we prove a Central Limit Theorem for the weight of the MSA with appropriate scaling. While the scaling for the CLT is similar to MST case explored by Janson, the centering required ($1$ as opposed to ζ(3) for Uniform[0,1] weights) and the limiting variance of the Gaussian ($1$ as opposed to $6ζ(4)-4ζ(3)$ for Uniform[0,1] weights) are notably different.
Related
- Hamiltonian graphs with prescribed minimum degree and no near-spanning cycles
- Spanning Trees with Many Leaves in Graphs of Minimum Degree at Least 7
- Directed distances in spanning-tree-decorated planar maps: exact exponent, scaling limit and universality
- Maximum and Minimum Spectral Radii in an Exceptional Family for Edge-Disjoint Spanning Trees
- Wild number for spanning trees in complete and complete bipartite graphs
BibTeX
@misc{bagchi2026weight,
title = {{CLT for the Weight of the Minimum Spanning Arborescence on the Complete Directed Graph}},
author = {Swarnadeep Bagchi and Pablo de la Fuente and Kesav Krishnan},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.00698},
eprint = {2611.00698},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.00698},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - CLT for the Weight of the Minimum Spanning Arborescence on the Complete Directed Graph
AU - Swarnadeep Bagchi
AU - Pablo de la Fuente
AU - Kesav Krishnan
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.00698
UR - https://arxiv.org/abs/2611.00698
AB - The minimum spanning arborescence (MSA) with a fixed boundary, defined on weighted directed graphs, is the directed analogue of the minimum spanning tree (MST). The behaviour of the MSA has been of recent interest and is known to be quite different from that of its undirected counterpart. On the complete directed graph, and for edge weights given by i.i.d. random variables with a broad class of distributions, we prove a Central Limit Theorem for the weight of the MSA with appropriate scaling. While the scaling for the CLT is similar to MST case explored by Janson, the centering required ($1$ as opposed to ζ(3) for Uniform[0,1] weights) and the limiting variance of the Gaussian ($1$ as opposed to $6ζ(4)-4ζ(3)$ for Uniform[0,1] weights) are notably different.
ER -