Freddie Illingworth

The Zarankiewicz problem in tripartite graphs

In 1975, Bollobás, Erdős, and Szemerédi asked the following Zarankiewicz-type problem. What is the smallest \tau such that an n \times n \times n tripartite graph with minimum degree n + \tau must contain K_{t, t, t}? They further conjectured that \tau = O(n^{1/2}) when t = 2. I will discuss our proof that \tau = O(n^{1 - 1/t}) (confirming their conjecture) and an infinite family of extremal examples. The bound O(n^{1 - 1/t}) is best possible whenever the Kővári-Sós-Turán bound \ex(n, K_{t, t}) = O(n^{2 - 1/t}) is (which is widely-conjectured to be the case). This is joint work with Francesco Di Braccio (LSE).