Universal limiting profile for successive minimum spanning tree forests

About 7 years old · traced to

For each k⩾1k\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 x∈Rx\in\mathbb R as k→∞k\to\infty. This predicts that the giant-component profiles become translates of one universal profile; the paper reports computational evidence, but no proof.

References

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.