Speaker: Raphy Yuster, U. Haifa Title: On some Ramsey type problems in tournaments Abstract: 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).
Mon, 01/04/2019 - 11:00 to 13:00
CS B-500, Safra campus