On the subgraph query problem

Abstract

Given a fixed graph $H$, a real number $p\in (0,1)$, and an infinite Erdős-Rényi graph $G\sim G(\infty ,p)$, how many adjacency queries do we have to make to find a copy of $H$ inside $G$ with probability $1/2$? Determining this number $f(H,p)$ is a variant of the {\it subgraph query problem} introduced by Ferber, Krivelevich, Sudakov, and Vieira. For every graph $H$, we improve the trivial upper bound of $f(H,p)=O(p^{-d})$, where $d$ is the degeneracy of $H$, by exhibiting an algorithm that finds a copy of $H$ in time $o(p^{-d})$ as $p$ goes to $0$. Furthermore, we prove that there are $2$-degenerate graphs which require $p^{-2+o(1)}$ queries, showing for the first time that there exist graphs $H$ for which $f(H,p)$ does not grow like a constant power of $p^{-1}$ as $p$ goes to $0$. Finally, we answer a question of Feige, Gamarnik, Neeman, Rácz, and Tetali by showing that for any $\delta <2$, there exists $\alpha <2$ such that one cannot find a clique of order $\alpha {\log }_{2}n$ in $G(n,1/2)$ in $n^{\delta }$ queries.

modified slightly after reviewer comments