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

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 n0Nn_0\in\mathbb{N} such that, for every nn0n\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], δnv(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.

Sources & referencesView supporting material

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.