  The $(m,n)$-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 on each turn and Painter immediately paints it red or
blue. Builder's goal is to force Painter to create either a red $K_m$ or a blue
$K_n$ using as few turns as possible. The online Ramsey number $\tilde{r}(m,n)$
is the minimum number of edges Builder needs to guarantee a win in the
$(m,n)$-online Ramsey game. By analyzing the special case where Painter plays
randomly, we obtain an exponential improvement \[ \tilde{r}(n,n) \ge
2^{(2-\sqrt{2})n + O(1)} \] for the lower bound on the diagonal online Ramsey
number, as well as a corresponding improvement \[ \tilde{r}(m,n) \ge
n^{(2-\sqrt{2})m + O(1)} \] for the off-diagonal case, where $m\ge 3$ is fixed
and $n\rightarrow\infty$. Using a different randomized Painter strategy, we
prove that $\tilde{r}(3,n)=\tilde{\Theta}(n^3)$, determining this function up
to a polylogarithmic factor. We also improve the upper bound in the
off-diagonal case for $m \geq 4$.
  In connection with the online Ramsey game with a random Painter, we study the
problem of finding a copy of a target graph $H$ in a sufficiently large unknown
Erd\H{o}s--R\'{e}nyi random graph $G(N,p)$ 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.

Combinatorics