The Taub Faculty of Computer Science Events and Talks

Abstract: The Ramsey number $r_k(s,n)$ is the minimum $N$ such that every red-blue coloring of the $k$-tuples of an $N$-element set contains either a red set of size $s$ or a blue set of size $n$, where a set is called red (blue) if all $k$-tuples from this set are red (blue). The problem of estimating Ramsey numbers is one of the central problems in modern Combinatorics and it has received a considerable amount of attention in the last 80 years.

In this talk we present new estimates for several basic hypergraph Ramsey problems. We prove a new upper bound for $r_k(s,n)$ for $k \geq 3$ and $s$ fixed, substantially improving previous best estimate of Erd\H{o}s and Rado from 1952. We also obtain a new lower bound for these numbers, showing in particular, that $r_3(4,n)$ has superexponential growth. This answers an open question posed by Erd\H{o}s and Hajnal in 1972. Finally, it time permits we report on progress which we made on related Ramsey-type problems.

Joint work with D. Conlon and J. Fox