Combinatorics: Raphy Yuster (U. Haifa) "On some Ramsey type problems in tournaments"

Mon, 01/04/201911:00-13:00
CS B-500, Safra campus
Speaker: Raphy Yuster, U. Haifa
Title: On some Ramsey type problems in tournaments
I will talk about several Ramsey type problems in tournaments guaranteeing the existence of subgraphs with certain chromatic properties.
Here are two such problems which attracted some attention recently:
1. Let g(n) be the smallest integer such that every tournament with more than g(n) vertices has an *acyclic subgraph* with chromatic number larger than n.
It is straightforward that Omega(n) <= g(n) <= n^2. An improvement of both bounds is presented.
2. 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. It is easy to show that r(h,k) >= (h-1)^k and in fact larger it is larger when k is small. We prove that indeed r(h,k) = (h − 1)^k when the number of colors k is large enough (roughly linear in h suffices).