Conjecture on packing families of bounded-degree trees with non-spanning members

About 5 years old · traced to

Let a tree family be a family (Ts)s∈[N](T_s)_{s\in[N]} of trees. Bounded-degree tree-family packing conjecture. There exist δ>0\delta>0 and n0∈Nn_0\in\mathbb{N} such that, for every n≥n0n\ge n_0, every tree family (Ts)s∈[N](T_s)_{s\in[N]} satisfying

Δ(Ts)≤n/2andv(Ts)≤nfor all s∈[N],\Delta(T_s)\le n/2\quad\text{and}\quad v(T_s)\le n\qquad\text{for all }s\in[N], δn≤v(Ts)≤(1−δ)nfor all s∈[δn],\delta n\le v(T_s)\le(1-\delta)n\qquad\text{for all }s\in[\delta n],

and

∑s∈[N]e(Ts)≤(n2)\sum_{s\in[N]}e(T_s)\le\binom{n}{2}

packs into KnK_n. This is motivated by necessary constraints on general tree families, including the need for many non-spanning trees; the paper does not report a resolution of this conjecture.

References

Primary source

Peter Allen, Julia Böttcher, Dennis Clemens, Jan Hladký, Diana Piguet and Anusch Taraz, “The tree packing conjecture for trees of almost linear maximum degree”, arXiv:2106.11720 (2022).

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.