On the subgraph query problem

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 $δ< 2$, there exists $α< 2$ such that one cannot find a clique of order $α\log_2 n$ in $G(n,1/2)$ in $n^δ$ queries.

No reviews yet.

No comments yet.