Monochromatic reachability in edge-colored tournaments (Solved)

Importance: High ✭✭✭
Author(s): Erdos, Paul
Recomm. for undergrads: no
Posted by: mdevos
on: July 9th, 2008
Solved by: Bousquet, Lochet, and Thomassé. A proof of the Erdős-Sands-Sauer-Woodrow conjecture https://arxiv.org/abs/1703.08123

\begin{problem} For every $n$, is there a (least) positive integer $f(n)$ so that whenever a tournament has its edges colored with $n$ colors, there exists a set $S$ of at most $f(n)$ vertices so that every vertex has a monochromatic path to some point in $S$? \end{problem}

This problem first appears in print in a lovely paper of Sands, Sauer, and Woodrow [SSW], where they prove that $f(2) = 1$. Actually, they prove a much stronger theorem. They show that for every 2-edge-colored digraph $G$ (even infinite) there exists an independent set $S \subseteq V(G)$ so that every vertex has a monochromatic path to some point in $S$.

It is open whether $f(k)$ is finite for every $k \ge 3$. The smallest open case, $k=3$, is already quite interesting; In [SSW] the authors ask if $f(3) = 3$.

Bibliography

*[SSW] B. Sands, N. Sauer, R. Woodrow, On monochromatic paths in edge-coloured digraphs. J. Combin. Theory Ser. B 33 (1982), no. 3, 271--275. \MRhref{MR0693367}.


* indicates original appearance(s) of problem.