{
  "id": "1911.04413",
  "version": "v1",
  "published": "2019-11-11T17:39:56.000Z",
  "updated": "2019-11-11T17:39:56.000Z",
  "title": "On the subgraph query problem",
  "authors": [
    "Ryan Alweiss",
    "Chady Ben Hamida",
    "Xiaoyu He",
    "Alexander Moreira"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Given a fixed graph $H$, a real number $p\\in(0,1)$, and an infinite Erd\\H{o}s-R\\'enyi 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\\'acz, 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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-11-11T17:39:56.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "subgraph query problem",
      "trivial upper bound",
      "constant power",
      "adjacency queries",
      "real number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}