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

Frequently asked questions

Doesn't specifying which vertices the rainbow tree sits on make the problem harder, not easier?

Yes -- the paper notes exactly this: finding a graceful labelling (which fixes the tree's vertices to be $\{0,\ldots,n\}$ ) is strictly harder than finding an unrestricted rainbow copy anywhere in $K_{2n+1}$ , which is why the authors work with the more flexible rainbow-embedding formulation rather than graceful labellings directly.

Source

Richard Montgomery, Alexey Pokrovskiy, and Benny Sudakov, 2020

A proof of Ringel's conjecture

arXiv:2001.02665v1

Condensed summary

Step 2 of 8: Rósa and Kotzig's shortcut: rainbow trees imply decompositions

Previous step Next step

In plain words

Instead of attacking the decomposition directly, colour every edge of $K_{2n+1}$ by its cyclic distance around a circle of $2n+1$ points labelled $0$ through $2n$ : edge $ij$ gets colour $k$ whenever the two endpoints are $k$ steps apart going one way around. If a single copy of the tree $T$ happens to use all $n$ colours exactly once (a "rainbow" copy), then simply rotating that one copy around the circle $2n+1$ times sweeps out $2n+1$ disjoint copies that use every edge of $K_{2n+1}$ -- because rotation preserves colours, and each colour class is used up exactly once per rotation.

\text{every ND-coloured } K_{2n+1} \text{ has a rainbow copy of every } n\text{-edge tree}

Detailed analysis

Rósa introduced the graceful-labelling approach to Ringel's conjecture, and Kotzig reformulated it in terms of rainbow subgraphs (Montgomery-Pokrovskiy-Sudakov 2021, Section 1). Fix the vertex set $\{0,\ldots,2n\}$ of $K_{2n+1}$ and define the near-distance (ND) colouring: $\text{colour edge } ij \text{ by } k \in [n] \text{ if } i \equiv j+k \text{ or } j \equiv i+k \pmod{2n+1}$ . Kotzig observed that if the ND-coloured $K_{2n+1}$ contains $\text{a rainbow copy of } T \text{ has all its } n \text{ edges in distinct colours}$ , then the $2n+1$ cyclic shifts of that one rainbow copy are pairwise edge-disjoint and together decompose $K_{2n+1}$ , since a shift only sends edges to other edges of the same colour. Kotzig further conjectured that a rainbow copy always exists; Montgomery, Pokrovskiy and Sudakov's Theorem 2.1 proves exactly this for large $n$ , which by Kotzig's observation immediately implies Ringel's Theorem 1.2.

Terms in this step

Rainbow subgraph: A subgraph of an edge-coloured graph in which every edge has a different colour.
ND-colouring (near-distance colouring): The edge-colouring of $K_{2n+1}$ on vertices $\{0,\ldots,2n\}$ that assigns colour $k$ to an edge whenever its endpoints are $k$ apart cyclically, for $k \in [n]$ .

Knowledge used in this step

Graphs, degree, and paths