Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-25T17:27:20.483Z Has data issue: false hasContentIssue false
  • English
  • Français

On the subgraph query problem

Part of: Extremal combinatorics Graph theory

Published online by Cambridge University Press:  27 July 2020

Ryan Alweiss ,
Chady Ben Hamida ,
Xiaoyu He  and
Alexander Moreira
Ryan Alweiss*
Affiliation:
Department of Mathematics, Princeton University, Princeton, NJ 08541, USA
Chady Ben Hamida
Affiliation:
Department of Mathematics, Princeton University, Princeton, NJ 08541, USA
Xiaoyu He
Affiliation:
Department of Mathematics, Stanford University, Stanford, CA 94305, USA
Alexander Moreira
Affiliation:
Department of Mathematics, Princeton University, Princeton, NJ 08541, USA
*
*Corresponding author. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

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 at least 1/2? Determining this number f(H, p) is a variant of the 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.

MSC classification

Primary: 05C57: Games on graphs
Secondary: 05C80: Random graphs 05D10: Ramsey theory
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 30 , Issue 1 , January 2021 , pp. 1 - 16
Check for updates
Copyright
© The Author(s), 2020. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

Research supported by an NSF Graduate Research Fellowship.

‡

Research supported by an NSF Graduate Research Fellowship.

References

Ajtai, M., Komlós, J. and Szemerédi, E. (1981) The longest path in a random graph. Combinatorica 1 1–12.CrossRefGoogle Scholar
Alon, N. and Spencer, J. H. (2008) The Probabilistic Method, third edition, Wiley.CrossRefGoogle Scholar
Bollobás, B. and Erdös, P. (1976) Cliques in random graphs. Math. Proc. Cambridge Philos. Soc. 80 419–427.Google Scholar
Burr, S. A. and Erdös, P. (1975) On the magnitude of generalized Ramsey numbers for graphs. In Infinite and Finite Sets I, Vol. 10 of Colloquia Mathematica Societatis János Bolyai, pp. 214–240, North-Holland.Google Scholar
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.Google Scholar
Feige, U., Gamarnik, D., Neeman, J., Rácz, M. Z. and Tetali, P. (2020) Finding cliques using few probes. Random Struct. Algorithms 56 142–153.CrossRefGoogle Scholar
Ferber, A., Krivelevich, M., Sudakov, B. and Vieira, P. (2016) Finding Hamilton cycles in random graphs with few queries. Random Struct. Algorithms 49 635–668.CrossRefGoogle Scholar
Ferber, A., Krivelevich, M., Sudakov, B. and Vieira, P. (2017) Finding paths in sparse random graphs requires many queries. Random Struct. Algorithms 50 71–85.Google Scholar
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–198, Schloss Dagstuhl–Leibniz-Zentrum für Informatik.Google Scholar
Hefetz, D., Krivelevich, M., Stojakovic, M. and Szabó, T. (2014) Positional Games, Birkhäuser.CrossRefGoogle Scholar
Krivelevich, M. (2014) Positional games. Proceedings of the International Congress of Mathematicians 3 355–379.Google Scholar
Lee, C. (2017) Ramsey numbers of degenerate graphs. Ann. of Math. 185 791–829.CrossRefGoogle Scholar
Pham, H. Personal communication.Google Scholar
Rácz, M. Z. and Schiffer, B. (2020) Finding a planted clique by adaptive probing. Random Struct. Algorithms 56 142–153.Google Scholar