Conjecture on optimal independent spanning trees in Erdős–Rényi graphs

Let GG(n,p)G\sim G(n,p) be an Erdős–Rényi random graph, and write δ(G)\delta(G) for its minimum degree. A spanning tree rooted at rr is an independent spanning tree (IST) family member when the paths from every vertex to rr in the different trees are pairwise internally vertex-disjoint. Conjecture on optimal independent spanning trees. Fix any plogn/np\geq \log n/n. Then, with high probability, for every vertex rV(G)r\in V(G), the graph GG contains δ(G)\delta(G) ISTs rooted at rr. This would extend the paper's asymptotic result to the threshold regime and attain the natural upper bound supplied by vertex connectivity, which equals the minimum degree in G(n,p)G(n,p) with high probability. The conjecture is posed as an open question.

Sources & referencesView supporting material

Primary source

Lawrence Hollom, Lyuben Lichev, Adva Mond, Julien Portier and Yiting Wang, “Approximate Itai-Zehavi conjecture for random graphs”, arXiv:2506.23970 (2025).

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.