Resilience conjecture for universality of bounded-degree spanning trees

From papers

Fix Δ2\Delta\ge 2 and γ>0\gamma>0. Let T(n,Δ)\mathcal{T}(n,\Delta) denote the family of spanning trees on nn vertices with maximum degree at most Δ\Delta. The local resilience of a graph with respect to a property is the largest number of incident edges that may be deleted at every vertex while the property is retained.

Bounded-degree tree universality resilience conjecture. The conclusion of the cited resilience theorem—that the local resilience of G(n,p)G(n,p) with respect to being universal for T(n,Δ)\mathcal{T}(n,\Delta) is almost surely at least 12γ\frac12-\gamma—holds for pClogn/np\ge C\log n/n.

The source says this probability is conjectured to be optimal up to constants, while the stated theorem only establishes the conclusion for pC(logn/n)1/3p\ge C(\log n/n)^{1/3}.

Progress summary

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

Sources & referencesView supporting material

Primary source

Julia Böttcher, “Large-scale structures in random graphs”, arXiv:1702.02648 (2017).

Solutions 0

No solutions have been posted yet.