A proof of the Erdos-Sands-Sauer-Woodrow conjecture

摘要

A very nice result of Barany and Lehel asserts that every finite subset X or R-d can be covered by h(d) X-boxes (i.e. each box has two antipodal points in X). As shown by Gyarfas and Palvolgyi this result would follow from the following conjecture: If a tournament admits a partition of its arc set into k quasi-orders, then its domination number is bounded in terms of k. This question is in turn implied by the Erdos-Sands-Sauer-Woodrow conjecture: If the arcs of a tournament T are coloured with k colour's, 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. (C) 2018 Elsevier Inc. All rights reserved.