We consider a variant of the planted clique problem where we are allowed unbounded computational time but can only investigate a small part of the graph by adaptive edge queries. We determine (up to logarithmic factors) the number of queries necessary both for detecting the presence of a planted clique and for finding the planted clique. Specifically, let @math be a random graph on @math vertices with a planted clique of size @math . We show that no algorithm that makes at most @math adaptive queries to the adjacency matrix of @math is likely to find the planted clique. On the other hand, when @math there exists a simple algorithm (with unbounded computational power) that finds the planted clique with high probability by making @math adaptive queries. For detection, the additive @math term is not necessary: the number of queries needed to detect the presence of a planted clique is @math (up to logarithmic factors).
Several recent works consider finding structure in a random graph under such an adaptive edge query model. Ferber, Krivelevich, Sudakov, and Vieira studied finding a Hamilton cycle @cite_5 and finding long paths @cite_10 , while Conlon, Fox, Grinshpun, and He @cite_12 studied finding a copy of a fixed target graph (such as a constant size clique). All of these works focus on sparse random graphs.
@cite_5 @cite_10 @cite_12
2963302945 2963995085 2811269531
We introduce a new setting of algorithmic problems in random graphs, studying the minimum number of queries one needs to ask about the adjacency between pairs of vertices of G(n,p) in order to typically find a subgraph possessing a given target property. We show that if p≥lnn+lnlnn+ω(1)n, then one can find a Hamilton cycle with high probability after exposing (1+o(1))n edges. Our result is tight in both p and the number of exposed edges. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 2016 We discuss a new algorithmic type of problem in random graphs studying the minimum number of queries one has to ask about adjacency between pairs of vertices of a random graph G∼G(n,p) in order to find a subgraph which possesses some target property with high probability. In this paper we focus on finding long paths in G∼G(n,p) when p=1+en for some fixed constant e>0 . This random graph is known to have typically linearly long paths. To have l edges with high probability in G∼G(n,p) one clearly needs to query at least Ω(lp) pairs of vertices. Can we find a path of length l economically, i.e., by querying roughly that many pairs? We argue that this is not possible and one needs to query significantly more pairs. We prove that any randomised algorithm which finds a path of length l=Ω(log(1e)e) with at least constant probability in G∼G(n,p) with p=1+en must query at least Ω(lpelog(1e)) pairs of vertices. This is tight up to the log(1e) factor. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 2016 The @math -online Ramsey game is a combinatorial game between two players, Builder and Painter. Starting from an infinite set of isolated vertices, Builder draws an edge at each step and Painter immediately paints the edge red or blue. Builder's goal is to force Painter to create either a red @math or a blue @math using as few edges as possible. The online Ramsey number @math is the minimum number of edges Builder needs to guarantee a win in the @math -online Ramsey game. By analyzing the special case where Painter plays randomly, we obtain an exponential improvement [ r (n,n) 2^ (2- 2 )n + O(1) ] for the lower bound on the diagonal online Ramsey number, as well as a corresponding improvement [ r (m,n) n^ (2- 2 )m + O(1) ] for the off-diagonal case, where @math is fixed and @math . Using a different randomized Painter strategy and the Lopsided Lov 'asz Local Lemma, we prove that @math , determining this function up to a polylogarithmic factor. We also improve the upper bound in the off-diagonal case for @math . In connection with the online Ramsey game with random Painter, we study the problem of finding a copy of a target graph @math in a sufficiently large unknown Erd o s--R ' e nyi random graph @math using as few queries as possible, where each query reveals whether or not a particular pair of vertices are adjacent. We call this problem the Subgraph Query Problem. We determine the order of the number of queries needed for complete graphs up to five vertices and prove general bounds for this problem.