The Random Turán Problem for Theta Graphs

Abstract

Given a graph $F$, we define $\mathrm{ex}(G_{n,p},F)$ to be the maximum number of edges in an $F$-free subgraph of the random graph $G_{n,p}$. Very little is known about $\mathrm{ex}(G_{n,p},F)$ when $F$ is bipartite, with essentially tight bounds known only when $F$ is either $C_4,C_6,C_{10}$, or $K_{s,t}$ with $t$ sufficiently large in terms of $s$, due to work of Füredi and of Morris and Saxton. We extend this work by establishing essentially tight bounds when $F$ is a theta graph with sufficiently many paths. Our main innovation is in proving a balanced supersaturation result for vertices, which differs from the standard approach of proving balanced supersaturation for edges.