Random Polynomial Graphs for Random Turán Problems

Abstract

Bukh and Conlon used random polynomial graphs to give effective lower bounds on $\mathrm{ex}(n,{\mathcal{T}}^{\ell })$, where ${\mathcal{T}}^{\ell }$ is the $\ell$th power of a balanced rooted tree $T$. We extend their result to give effective lower bounds on $\mathrm{ex}(G_{n,p},{\mathcal{T}}^{\ell })$, which is the maximum number of edges in a ${\mathcal{T}}^{\ell }$-free subgraph of the random graph $G_{n,p}$. Analogous bounds for generalized Turán numbers in random graphs are also proven.

16 pages; corrected the bound on p assumed in Theorems 1.2 and 1.3