A proof of the Erdos-Sands-Sauer-Woodrow conjecture
Résumé
A very nice result of Barany and Lehel asserts that every finite subset $X$ or $R^d$ can be covered
by $f(d)$ $X$-boxes (i.e. each box has two antipodal points in $X$). As shown by Gy\'arf\'as and
P\'alv\H{o}lgyi this result would follow from the following conjecture : If a tournament admits
a partition of its arc set into $k$ partial orders, then its domination number is bounded in terms of $k$.
This question is in turn implied by the Erd\H{o}s-Sands-Sauer-Woodrow conjecture : If the arcs of a tournament $T$ are colored with $k$ colors, there is a set $X$ of at most $g(k)$ vertices such that for every vertex $v$ of $T$, there is a monochromatic path from $X$ to $v$. We give a short proof of this statement. We moreover show that the general Sands-Sauer-Woodrow conjecture (which as a special case implies the stable marriage theorem) is valid for directed graphs with bounded stability number. This conjecture remains however open.