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

Frequently asked questions

Why embed a slightly smaller forest

T'

instead of the whole tree

T

right away?

Embedding the full tree $T$ directly would use up every colour and vertex simultaneously, leaving no room to manoeuvre; by holding back a small special part (the leaves or bare-path ends from the case division), the argument keeps a controllable random reserve of vertices and colours to finish the job precisely in Step 5.

Source

Richard Montgomery, Alexey Pokrovskiy, and Benny Sudakov, 2020

A proof of Ringel's conjecture

arXiv:2001.02665v1

Condensed summary

Step 4 of 8: Method M1: randomly embedding almost all of the tree

Previous step Next step

In plain words

Rather than trying to place the whole tree $T$ at once, the authors first place a slightly smaller version $T'$ (missing only the special leaves or bare-path ends singled out by the case division) as a rainbow copy chosen at random among many valid placements. Randomness is the key trick: instead of tracking exactly which vertices and colours end up unused, the authors only need to know that a large, well-behaved random leftover set of vertices and colours remains, ready to absorb the missing piece.

(1-\epsilon)n

Detailed analysis

Montgomery, Pokrovskiy and Sudakov (2021, Section 2.1, building on their earlier paper [Montgomery-Pokrovskiy-Sudakov, prior work]) prove Theorem 2.2: for a $2$ -factorised ND-colouring of $K_{2n+1}$ and a forest $T'$ on $(1-\epsilon)n$ vertices, there is a randomised rainbow copy $\hat{T}'$ of $T'$ , together with random subsets $V \subseteq V(K_{2n+1})\setminus V(\hat{T}'), \ C \subseteq C(K_{2n+1})\setminus C(\hat{T}')$ , such that $\hat{T}'$ is rainbow with high probability, and both $V$ and $C$ are provably "nicely random" (each element appears independently with a fixed probability). This lets the argument avoid tracking exact leftover vertices and colours, working instead with their statistical distribution.

Terms in this step

2-factorised colouring: An edge-colouring of $K_{2n+1}$ in which every vertex is adjacent to exactly $2$ edges of each colour; the ND-colouring has this property.
q-random set: A random subset of a ground set in which each element appears independently with the same fixed probability $q$ , making its statistical behaviour easy to control.

Knowledge used in this step

The probabilistic method