The Random Tur\'an Problem for Theta Graphs

MaRDI QIDQ6438067zbMATH OpenFDO

Authors Gwen McKinley, Sam Spiro

Publication date 25 May 2023

Abstract: Given a graph $F$, we define $operatornameex(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 $operatornameex(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"uredi 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.

This page was built for publication: The Random Tur\'an Problem for Theta Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6438067)