Worked solution: A rainbow-tree proof of Ringel's conjecture (2020)

Frequently asked questions

Does Method M3 prove Rósa's graceful labelling conjecture too?

Not quite: M3 produces a rainbow copy of $T$ in the ND-colouring, which is a weaker requirement than a graceful labelling (which additionally fixes the tree's vertices to occupy exactly $\{0,\ldots,n\}$ ), so Case C trees get a full Ringel-style embedding without the paper needing to resolve the graceful labelling conjecture itself.

Source

Richard Montgomery, Alexey Pokrovskiy, and Benny Sudakov, 2020

A proof of Ringel's conjecture

arXiv:2001.02665v1

Condensed summary

Step 6 of 8: Method M3: a fully deterministic embedding for Case C

Previous step Next step

In plain words

A Case C tree is dominated by a handful of extremely high-degree "hub" vertices, and randomness struggles here: with so few structural pieces to shuffle around, a random placement offers no meaningful independence to exploit. So the authors switch strategy entirely for this case, giving up on randomness and instead constructing the rainbow embedding by hand, vertex by vertex, in a way that closely mirrors the classical graceful-labelling technique.

\text{removing leaves next to vertices of degree} \ge \delta^{-4} \text{ leaves a tree with at most } n/100 \text{ vertices}

Detailed analysis

Section 7 of Montgomery, Pokrovskiy and Sudakov (2021) handles Case C trees, i.e. those where removing leaves adjacent to vertices of degree at least $\delta^{-4}$ leaves at most $n/100$ vertices, meaning the tree is essentially a small core with huge stars attached. For such trees the authors give up randomisation and instead construct a rainbow embedding completely deterministically, carefully choosing an explicit vertex ordering and colour assignment that is, in the authors' words, "something very close to a graceful labelling" of $T$ ; this method is essentially independent of the random techniques (M1, M2) used for Cases A and B.

Terms in this step

Graceful labelling: A bijective labelling $f: V(T) \to \{0,\ldots,n\}$ of a tree's vertices such that the edge differences $|f(x)-f(y)|$ are all distinct; Rosa conjectured every tree has one, and it directly yields a rainbow copy in the ND-colouring.