Cioabă and Wong's spectral spanning-tree packing conjecture

Let m1m\geq 1 be an integer, and let GG be a dd-regular graph with d2m+2d\geq 2m+2. Let λ2(G)\lambda_2(G) be the second-largest adjacency eigenvalue of GG, and let σ(G)\sigma(G) denote the maximum number of edge-disjoint spanning trees in GG. Cioabă and Wong's conjecture. If

λ2(G)<d2m+1d+1,\lambda_2(G)<d-\frac{2m+1}{d+1},

then

σ(G)m+1.\sigma(G)\geq m+1.

This conjecture gives a factor-of-two improvement over the earlier spectral condition implying the existence of m+1m+1 edge-disjoint spanning trees; it was verified for m{1,2}m\in\{1,2\}, while the paper constructs examples showing that the conjectured bound is essentially best possible.

Sources & referencesView supporting material

Primary source

Sebastian M. Cioabă, Anthony Ostuni, Davin Park, Sriya Potluri, Tanay Wakhare and Wiseley Wong, “Extremal Graphs for a Spectral Inequality on Edge-Disjoint Spanning Trees”, arXiv:2104.01665 (2021).

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.