Oriented Ramsey numbers of graded digraphs

Abstract

We show that any graded digraph $D$ on $n$ vertices with maximum degree $\Delta$ has an oriented Ramsey number of at most $C^{\Delta }n$ for some absolute constant $C>1$, improving upon a recent result of Fox, He, and Wigderson. In particular, this implies that oriented grids in any fixed dimension have linear oriented Ramsey numbers, and gives a polynomial bound on the oriented Ramsey number of the hypercube. We also show that this result is essentially best possible, in that there exist graded digraphs on $n$ vertices with maximum degree $\Delta$ such that their oriented Ramsey number is at least $c^{\Delta }n$ for some absolute constant $c>1$.

20 pages