Date:

Mon, 01/04/201911:00-13:00

Location:

CS B-500, Safra campus

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).

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).