Universal limiting profile for successive minimum spanning tree forests

For each k1k\geqslant1, let Fk(t)F_k(t) be the forest produced by Kruskal's algorithm at time tt, and let ρk(t)\rho_k(t) be the limiting fraction of vertices in its largest component. The functions ρk\rho_k describe the giant-component sizes of the successive forests. Universal profile conjecture. There exists a continuous increasing function ρ:(,)[0,1)\rho_\infty:(-\infty,\infty)\to[0,1) such that

ρk(2k+x)ρ(x)\rho_k(2k+x)\to\rho_\infty(x)

uniformly in xRx\in\mathbb R as kk\to\infty. This predicts that the giant-component profiles become translates of one universal profile; the paper reports computational evidence, but no proof.

Sources & referencesView supporting material

Primary source

Svante Janson and Gregory B. Sorkin, “Successive minimum spanning trees”, arXiv:1906.01533 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.