On the subgraph query problem
Given a fixed graph H, a real number p∈(0,1), and an infinite Erdős-Rényi graph G∼G(∞,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 αlog2n in G(n,1/2) in nδ queries.
