Weight of a link in a shortest path tree and the dedekind eta function

Research output: Chapter in Book/Conference proceedings/Edited volumeChapterScientific

1 Citation (Scopus)

Abstract

The weight of a randomly chosen link in the shortest path tree on the complete graph with exponential i.i.d. link weights is studied. The corresponding exact probability generating function and the asymptotic law are derived. As a remarkable coincidence, this asymptotic law is precisely the same as the distribution of the cost of one job in the random assignment problem. We also show that the asymptotic (scaled) maximum interattachment time to that shortest path tree, which is a uniform recursive tree, equals the square of the Dedekind Eta function, a central function in modular forms, elliptic functions, and the theory of partitions.
Original languageEnglish
Title of host publicationRandom Structures and Algorithms
Editors s.n.
Place of Publications.l.
PublisherWiley
Pages-
Number of pages30
DOIs
Publication statusPublished - 2010

Keywords

  • edited works: contributions
  • Boekdeel internat.wet

Fingerprint Dive into the research topics of 'Weight of a link in a shortest path tree and the dedekind eta function'. Together they form a unique fingerprint.

Cite this