Open Collections

Improved bounds for the Brown-Erdos-Sos problem

Banff International Research Station for Mathematical Innovation and Discovery

Let $f_r(n, v, e)$ be the maximum number of edges in an $r$-uniform hypergraph on $n$ vertices which contains no induced subgraph with $v$ vertices and at least $e$ edges. The Brown--Erd\H{o}s--S\'os problem of determining $f_r(n, v, e)$ is a central question in extremal combinatorics, with surprising connections to a number of seemingly unrelated areas. For example, the result of Ruzsa and Szemer\'edi that $f_3(n, 6, 3) = o(n^2)$ implies Roth's theorem on the existence of $3$-term arithmetic progressions in dense subsets of the integers. As a generalisation of this result, it is conjectured that $$f_r(n, e(r-k) + k + 1, e) = o(n^k)$$ for any fixed $r > k \geq 2$ and $e \geq 3$. The best progress towards this conjecture, due to S\'ark\"ozy and Selkow, says that $$f_r(n, e(r-k) + k + \lfloor \log e\rfloor, e) = o(n^k),$$ where the $\log$ is taken base two. In this talk, we will discuss a recent improvement to this bound.

Mathematics; Combinatorics; Probability theory and stochastic processes

video/mp4

Author affiliation: California Institute of Technology

2020-03-03

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/73669

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/