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.