Covering 2-colored complete digraphs by monochromatic $d$-dominating digraphs

Abstract

A digraph is {\em $d$-dominating} if every set of at most $d$ vertices has a common out-neighbor. For all integers $d\ge 2$, let $f(d)$ be the smallest integer such that the vertices of every 2-edge-colored (finite or infinite) complete digraph (including loops) can be covered by the vertices of at most $f(d)$ monochromatic $d$-dominating subgraphs. Note that the existence of $f(d)$ is not obvious -- indeed, the question which motivated this paper was simply to determine whether $f(d)$ is bounded, even for $d=2$. We answer this question affirmatively for all $d\ge 2$, proving $4\le f(2)\le 8$ and $2d\le f(d)\le 2d\left(\frac{d^d-1}{d-1}\right)$ for all $d\ge 3$. We also give an example to show that there is no analogous bound for more than two colors. Our result provides a positive answer to a question regarding an infinite analogue of the Burr-Erdős conjecture on the Ramsey numbers of $d$-degenerate graphs. Moreover, a special case of our result is related to properties of $d$-paradoxical tournaments.

7 pages