{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T09:47:27Z","timestamp":1778924847157,"version":"3.51.4"},"reference-count":14,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2020,7,27]],"date-time":"2020-07-27T00:00:00Z","timestamp":1595808000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Given a fixed graph <jats:italic>H<\/jats:italic>, a real number <jats:italic>p<\/jats:italic>  (0, 1) and an infinite Erd\u00f6s\u2013R\u00e9nyi graph <jats:italic>G<\/jats:italic> \u223c <jats:italic>G<\/jats:italic>(\u221e, <jats:italic>p<\/jats:italic>), how many adjacency queries do we have to make to find a copy of <jats:italic>H<\/jats:italic> inside <jats:italic>G<\/jats:italic> with probability at least 1\/2? Determining this number <jats:italic>f<\/jats:italic>(<jats:italic>H<\/jats:italic>, <jats:italic>p<\/jats:italic>) is a variant of the <jats:italic>subgraph query problem<\/jats:italic> introduced by Ferber, Krivelevich, Sudakov and Vieira. For every graph <jats:italic>H<\/jats:italic>, we improve the trivial upper bound of <jats:italic>f<\/jats:italic>(<jats:italic>H<\/jats:italic>, <jats:italic>p<\/jats:italic>) = <jats:italic>O<\/jats:italic>(<jats:italic>p<\/jats:italic><jats:sup>\u2212<jats:italic>d<\/jats:italic><\/jats:sup>), where <jats:italic>d<\/jats:italic> is the degeneracy of <jats:italic>H<\/jats:italic>, by exhibiting an algorithm that finds a copy of <jats:italic>H<\/jats:italic> in time <jats:italic>O<\/jats:italic>(<jats:italic>p<\/jats:italic><jats:sup>\u2212<jats:italic>d<\/jats:italic><\/jats:sup>) as <jats:italic>p<\/jats:italic> goes to 0. Furthermore, we prove that there are 2-degenerate graphs which require <jats:italic>p<\/jats:italic><jats:sup>\u22122+<jats:italic>o<\/jats:italic>(1)<\/jats:sup> queries, showing for the first time that there exist graphs <jats:italic>H<\/jats:italic> for which <jats:italic>f<\/jats:italic>(<jats:italic>H<\/jats:italic>, <jats:italic>p<\/jats:italic>) does not grow like a constant power of <jats:italic>p<\/jats:italic><jats:sup>\u22121<\/jats:sup> as <jats:italic>p<\/jats:italic> goes to 0. Finally, we answer a question of Feige, Gamarnik, Neeman, R\u00e1cz and Tetali by showing that for any <jats:italic>\u03b4<\/jats:italic> &lt; 2, there exists <jats:italic>\u03b1<\/jats:italic> &lt; 2 such that one cannot find a clique of order <jats:italic>\u03b1<\/jats:italic> log<jats:sub>2<\/jats:sub><jats:italic>n<\/jats:italic> in <jats:italic>G<\/jats:italic>(<jats:italic>n<\/jats:italic>, 1\/2) in <jats:italic>n<\/jats:italic><jats:sup><jats:italic>\u03b4<\/jats:italic><\/jats:sup> queries.<\/jats:p>","DOI":"10.1017\/s0963548320000218","type":"journal-article","created":{"date-parts":[[2020,7,27]],"date-time":"2020-07-27T07:25:00Z","timestamp":1595834700000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":2,"title":["On the subgraph query problem"],"prefix":"10.1017","volume":"30","author":[{"given":"Ryan","family":"Alweiss","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chady Ben","family":"Hamida","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaoyu","family":"He","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Moreira","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2020,7,27]]},"reference":[{"key":"S0963548320000218_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-0825-5"},{"key":"S0963548320000218_ref14","first-page":"142","article-title":"Finding a planted clique by adaptive probing","volume":"56","author":"R\u00e1cz","year":"2020","journal-title":"Random Struct. Algorithms"},{"key":"S0963548320000218_ref5","doi-asserted-by":"crossref","unstructured":"[5] Conlon, D. , Fox, J. , Grinshpun, A. and He, X. (2019) Online Ramsey numbers and the subgraph query problem. In Building Bridges II, Vol. 28 of Bolyai Society Mathematical Studies, Springer.","DOI":"10.1007\/978-3-662-59204-5_4"},{"key":"S0963548320000218_ref13","unstructured":"[13] Pham, H. Personal communication."},{"key":"S0963548320000218_ref8","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1002\/rsa.20680","article-title":"Finding paths in sparse random graphs requires many queries","volume":"50","author":"Ferber","year":"2017","journal-title":"Random Struct. Algorithms"},{"key":"S0963548320000218_ref2","doi-asserted-by":"publisher","DOI":"10.1002\/9780470277331"},{"key":"S0963548320000218_ref6","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20896"},{"key":"S0963548320000218_ref3","unstructured":"[3] Bollob\u00e1s, B. and Erd\u00f6s, P. (1976) Cliques in random graphs. Math. Proc. Cambridge Philos. Soc. 80 419\u2013427."},{"key":"S0963548320000218_ref9","unstructured":"[9] Frieze, A. and Kannan, R. (2008) A new approach to the planted clique problem. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Vol. 2, pp. 187\u2013198, Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik."},{"key":"S0963548320000218_ref7","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20679"},{"key":"S0963548320000218_ref12","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2017.185.3.2"},{"key":"S0963548320000218_ref11","unstructured":"[11] Krivelevich, M. (2014) Positional games. Proceedings of the International Congress of Mathematicians 3 355\u2013379."},{"key":"S0963548320000218_ref4","unstructured":"[4] Burr, S. A. and Erd\u00f6s, P. (1975) On the magnitude of generalized Ramsey numbers for graphs. In Infinite and Finite Sets I, Vol. 10 of Colloquia Mathematica Societatis J\u00e1nos Bolyai, pp. 214\u2013240, North-Holland."},{"key":"S0963548320000218_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579172"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000218","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,21]],"date-time":"2021-01-21T11:50:24Z","timestamp":1611229824000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000218\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,27]]},"references-count":14,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["S0963548320000218"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000218","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,27]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}