Resilience conjecture for universality of bounded-degree spanning trees
Resilience conjecture for universality of bounded-degree spanning trees
Fix and . Let denote the family of spanning trees on vertices with maximum degree at most . 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 with respect to being universal for is almost surely at least —holds for .
The source says this probability is conjectured to be optimal up to constants, while the stated theorem only establishes the conclusion for .
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
Sign in to submit a solution.
No solutions have been posted yet.