# Polynomial to exponential transition in Ramsey theory

Dhruv Mubayi

## Affiliation:

University of Illinois at Chicago

## Date:

Thu, 20/06/2019 - 1:00pm

## Venue:

RC-4082, The Red Centre, UNSW

## Abstract:

After a brief introduction to classical hypergraph Ramsey numbers, I will focus on the following problem. What is the minimum $t$ such that there exist arbitrarily large $k$-uniform hypergraphs whose independence number is at most polylogarithmic in the number of vertices and every $s$ vertices span at most $t$ edges? Erdos and Hajnal conjectured (1972) that this minimum can be calculated precisely using a recursive formula and Erdos offered a \$500 prize for a proof. For$k = 3$, this has been settled for many values of s, but it was not known for larger$k$. Here we settle the conjecture for all$k\$ at least 4. Our method also answers a question of Bhat and Rodl about the maximum upper density of quasirandom hypergraphs.

This is joint work with Alexander Razborov.