Combinatorics Seminar

When: Sunday, December 11, 10am
Where: Schreiber 309
Speaker: Raphy Yuster, University of Haifa
Title: A Ramsey-type result for oriented trees

Abstract:

Given positive integers h and k, denote by r(h,k) the smallest integer n such that in any k-coloring of the edges of a tournament on more than n vertices there is a monochromatic copy of every oriented tree on h vertices. The value r(h,1) is not yet known for all h.

We prove that r(h,k) = (h-1)^k for all k sufficiently large (in fact k=\Theta(h \log h) suffices).

The related parameter r*(h,k), where some color contains all oriented trees, is asymptotically determined.

Values of r(h,2) for some small h are also established.