Talk information

Date: Sunday, May 31, 2026
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Asaf Cohen Antonir (Tel Aviv University)
Title: Universality for bounded degree trees in random graphs

Abstract:

A graph on $n$ vertices is said to be $D$-universal if it contains a copy of every $n$-vertex tree with maximum degree at most $D$. Solving a long standing open problem, we show that there exists a universal constant $C>0$ such that, for every $D > 2$, asymptotically almost surely, the binomial random graph $G(n,C(\ln n)/n)$ is $D$-universal.

Our proof uses absorption methods as well as novel embedding algorithms in random settings. Our framework is fairly versatile and allows to find various spanning subgraphs in sparse random graphs.

The talk will be based on joint work with Lyuben Lichev and Maksim Zhukovskii.