Abstract
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 \ge 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ős–Ré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.
Access provided by Autonomous University of Puebla. Download chapter PDF
Similar content being viewed by others
Keywords
Subject Classifications
1 Introduction
The Ramsey number r(m, n) is the minimum integer N such that every red/blue-coloring of the edges of the complete graph \(K_N\) on N vertices contains either a red \(K_m\) or a blue \(K_n\). Ramsey’s theorem guarantees the existence of r(m, n) and determining or estimating Ramsey numbers is a central problem in combinatorics. Classical results of Erdős–Szekeres and Erdős imply that \(2^{n/2} \le r(n,n) \le 2^{2n}\) for \(n \ge 2\). The only improvements to these bounds over the last seventy years have been to lower order terms (see [9, 26]), with the best known lower bound coming from an application of the Lovász local lemma [14].
Off-diagonal Ramsey numbers, where m is fixed and n tends to infinity, have also received considerable attention. In progress that has closely mirrored and often instigated advances on the probabilistic method, we now know that
The lower bound here is due to Kim [21] and the upper bound to Ajtai, Komlós and Szemerédi [1]. Recently, Bohman and Keevash [8] and, independently, Fiz Pontiveros, Griffiths and Morris [18] improved the constant in Kim’s lower bound via careful analysis of the triangle-free process, determining r(3, n) up to a factor of \(4+o(1)\).
More generally, for \(m\ge 4\) fixed and n growing, the best known lower bound is
proved by Bohman and Keevash [7] using the H-free process, while the best upper bound in this setting is
again due to Ajtai, Komlós and Szemerédi [1]. Here the subscripts denote the variable(s) that the implicit constant is allowed to depend on.
There are many interesting variants of the classical Ramsey problem. One such variant is the size Ramsey number \(\hat{r}(m, n)\), defined as the smallest N for which there exists a graph G with N edges such that every red/blue-coloring of the edges of G contains either a red \(K_m\) or a blue \(K_n\). It was shown by Chvátal (see Theorem 1 in the foundational paper of Erdős, Faudree, Rousseau and Schelp [13]) that \(\hat{r}(m, n)\) is just the number of edges in the complete graph on r(m, n) vertices, that is,
We will be concerned with a much-studied game-theoretic variant of the size Ramsey number, introduced independently by Beck [4] and by Kurek and Ruciński [25]. The (m, n)-online Ramsey game is a game between two players, Builder and Painter, on an infinite set of initially isolated vertices. Each turn, Builder places an edge between two nonadjacent vertices and Painter immediately paints it either red or blue. The online Ramsey number \(\tilde{r}(m,n)\) is then the smallest number of turns N that Builder needs to guarantee the existence of either a red \(K_m\) or a blue \(K_n\).
It is a simple exercise to show that \(\tilde{r}(m,n)\) is related to the usual Ramsey number r(m, n) by
In the diagonal case, the upper bound in (1) has been improved by Conlon [10], who showed that for infinitely many n,
The main result of this paper is a new lower bound for online Ramsey numbers.
Theorem 1.1
If, for some \(m,n,N\ge 1\), there exist \(p\in (0,1)\), \(c\le \frac{1}{2}m\), and \(d\le \frac{1}{2}n\) for which
then \(\tilde{r}(m,n)>N\).
In particular, if \(\tilde{r}(n) :=\tilde{r}(n,n)\) is the diagonal online Ramsey number, Theorem 1.1 can be used to improve the classical bound \(\tilde{r}(n) \ge 2^{n/2 - 1}\) by an exponential factor. Indeed, taking \(p=\frac{1}{2}\) and \(c = d \approx (1-\frac{1}{\sqrt{2}})n\) in Theorem 1.1, we get the following immediate corollary.
Corollary 1.2
For the diagonal online Ramsey numbers \(\tilde{r}(n)\),
As for the off-diagonal case, when m is fixed and \(n\rightarrow \infty \), Theorem 1.1 can be also used to substantially improve the best-known lower bound. In this case, we take \(c\approx (1-\frac{1}{\sqrt{2}})m\), \(d=0\), and \(p=C\frac{m\log n}{n}\) for a sufficiently large \(C>0\) to obtain the following corollary.
Corollary 1.3
For fixed \(m\ge 3\) and n sufficiently large in terms of m,
For general m, Corollary 1.3 gives the best known lower bounds for the off-diagonal online Ramsey number. However, it is possible to do better for \(m=3\) by using a smarter Painter strategy which deliberately avoids building red triangles.
Theorem 1.4
For \(n\rightarrow \infty \),
Roughly speaking, Painter’s strategy is to paint every edge blue initially, but to switch to painting randomly if both endpoints of a freshly built edge have high degree. Also, when presented with an edge that would complete a red triangle, Painter always paints it blue. The bound given in Theorem 1.4 is n times the bound on the usual Ramsey number that comes from applying the Lovász Local Lemma [14]. However, our argument is closer in spirit to an earlier proof of the same bound given by Erdős [12] using alterations. This method for lower bounding r(3, n) was later generalized to all r(m, n) by Krivelevich [22] and we suspect that Theorem 1.4 can be generalized to \(\tilde{r}(m,n)\) in the same way.
In the other direction, we prove a new upper bound on the off-diagonal online Ramsey number.
Theorem 1.5
For any fixed \(m\ge 3\),
In particular, note that Theorems 1.4 and 1.5 determine the asymptotic growth rate of \(\tilde{r}(3,n)\) up to a polylogarithmic factor, namely,
Theorem 1.5 has a similar flavor to the improvement on diagonal online Ramsey numbers made by the first author [10] and work on the so-called vertex online Ramsey numbers due to Conlon, Fox and Sudakov [11]. It is obtained by adapting the standard Erdős–Szekeres proof of Ramsey’s theorem to the online setting and applying a classical result of Ajtai, Komlós and Szemerédi [1] bounding r(m, n).
In order to prove Theorem 1.1, we specialize to the case where Painter plays randomly. This is sufficient because Builder, who we may assume has unlimited computational resources, will always respond in the best possible manner to Painter’s moves. Therefore, if a random Painter can stop this perfect Builder from winning within a certain number of moves with positive probability, an explicit strategy exists by which Painter can delay the game up to this point. This motivates the following key definition.
Definition 1.6
For \(m,n \ge 3\) and \(p\in (0,1)\), define \(\tilde{r}(m,n;p)\) to be the number of turns Builder needs to win the (m, n)-online Ramsey game with probability at least \(\frac{1}{2}\) against a Painter who independently paints each edge red with probability p and blue with probability \(1-p\). The online random Ramsey number \(\tilde{r}_{\text {rand}}(m,n)\) is the maximum value of \(\tilde{r}(m,n;p)\) over \(p\in (0,1)\).
We note that there is a rich literature on simplifying the study of various combinatorial games by specializing to the case where one or both players play randomly (see [5, 20, 23]). For example, a variant of the online Ramsey game with random Builder instead of random Painter was studied by E. Friedgut, Y. Kohayakawa, V. Rödl, A. Ruciński and P. Tetali [19].
We make the following conjectures about the growth rate of \(\tilde{r}_{\text {rand}}(m,n)\).
Conjecture 1.7
-
(a)
The diagonal online random Ramsey numbers satisfy
$$ \tilde{r}_{\text { rand}}(n,n) = 2^{(1+o(1))\frac{2}{3}n}. $$ -
(b)
The off-diagonal online random Ramsey numbers (\(m\ge 3\) fixed and \(n\rightarrow \infty \)) satisfy
$$ \tilde{r}_{\text { rand}}(m,n) = n^{(1+o(1))\frac{2}{3}m}. $$
These conjectures are motivated by a connection with another problem, which we now describe.
Let \(p\in (0, 1)\) be a fixed probability and suppose Builder plays the following one-player game, which we call the Subgraph Query Game, on the random graph \(G(\mathbb {Z},p)\) with infinitely many vertices. The edges of the graph are initially hidden. At each step, Builder queries a single pair of vertices and is told whether the pair is an edge of the graph or not. Equivalently, the graph starts out empty and each edge is successfully built by Builder with probability p (each edge may be queried at most once). In what follows, we use the terms “query” and “build” interchangeably.
Builder’s goal is to find a copy of a given graph H in the ambient random graph as quickly as possible. We call this problem of minimizing the number of steps in the Subgraph Query Game the Subgraph Query Problem. When \(H = K_m\), this may be seen as a variant of the online random Ramsey game, but where Builder is only interested in finding a red copy of \(K_m\).
A version of this problem was studied independently by Ferber, Krivelevich, Sudakov and Vieira [16, 17], although they were interested in querying for long paths and cycles in G(n, p). For instance, they showed that if \(p \ge \frac{\log n + \log \log n + \omega (1)}{n}\), then it is possible to find a Hamiltonian cycle with high probability in G(n, p) after \((1+o(1))n\) positive answers. In contrast, we are mainly interested in the setting where H is a fixed graph to be found in a much larger random graph.
Definition 1.8
If \(p\in (0,1)\), define f(H, p) to be the minimum (over all Builder strategies) number of turns Builder needs to be able to build a copy of H with probability at least 1/2 in the Subgraph Query Game, if each edge is built successfully with probability p.
It might appear equally reasonable to study the minimum number of turns in which one can build at least one copy of H in expectation. However, for certain H, such as a clique \(K_m\) together with many leaves off a single vertex, it is possible to describe a strategy which has a tiny probability of successfully constructing copies of H, but upon success immediately builds a large number of copies, attaining low success probability but high expectation. Such a strategy is undesirable for application to online random Ramsey numbers, so we use the first definition instead.
Conjecture 1.7 is motivated by the following conjecture regarding \(f(K_m, p)\). The upper bound in this conjecture is proved in Sect. 5.2.
Conjecture 1.9
For any \(m \ge 4\),
where
The following result shows that the Subgraph Query Problem and the online random Ramsey game are closely related.
Theorem 1.10
For any \(m,n\ge 3\) and \(p\in (0,1)\),
Using Theorem 1.10, we can show that Conjecture 1.9 implies both cases of Conjecture 1.7. We can also determine an approximately optimal value for the probability parameter p in the online Ramsey game with random Painter.
Theorem 1.11
For \(m\ge 3\) fixed and \(n\rightarrow \infty \), there exists a \(p = \Theta (m/n\log (n/m))\) for which
We say that a graph has a k-matching if it contains k vertex-disjoint edges. Our main result on the Subgraph Query Problem shows that graphs with large matchings are hard to build in few steps. We write V(H) and E(H) for the vertices and edges of H and let \(v(H) = |V(H)|\) and \(e(H)=|E(H)|\).
Theorem 1.12
If H is a graph that contains a k-matching, then
Together with the upper bound construction described in Sect. 5.2, this is enough to settle the growth rate of \(f(K_m, p)\) for \(m\le 5\). In particular, it proves Conjecture 1.9 for \(m=4, 5\).
Theorem 1.13
The asymptotic growth rates of \(f(K_m, p)\) for \(m=3,4,5\) are
Asymptotically, \(k = (1-1/\sqrt{2})m\) is the optimal k to pick in Theorem 1.12. With this value, we get the following bound on \(f(K_m, p)\) which corresponds to Corollaries 1.2 and 1.3 in the online Ramsey number setting.
Corollary 1.14
For all \(m\ge 3\),
In studying the function f(H, p), we were naturally led to consider the following function. When H is a graph with no isolated vertices, define t(H, p, N) to be the maximum expected number of copies of H that can be built in N moves in the Subgraph Query Game with parameter p, the maximum taken over all possible Builder strategies.
However, if H has isolated vertices, the expected value is zero or infinite. Instead, if H has exactly k isolated vertices \(v_1,\ldots ,v_k\), we define
to capture the fact that the game with N turns involves at most 2N vertices and therefore might as well be played on 2N fixed vertices.
Studying the threshold value of N for which \(t(H,p,N) \ge 1\) leads to Theorem 1.12 above. Intuitively, we expect the best strategy for building a copy of H to be the same as the one which expects to build a single copy of H in as few turns as possible.
Another natural question about the function t(H, p, N) is: if N is very large, what is the maximum number of copies Builder can expect to build in the Subgraph Query Game? Here we show that for N sufficiently large the strategy of taking \(O(\sqrt{2N})\) vertices and building all pairs of edges between them is asymptotically optimal for maximising \(t(K_m,p,N)\), even though it is decidedly suboptimal for trying to build a single copy of \(K_m\).
Theorem 1.15
For all \(m\ge 2, p \in (0,1), \varepsilon >0\), there exists \(C > 0\) such that if \(N\ge Cp^{-(2m-1)}(\log (p^{-1}))^2\), then
The rest of the paper is organized as follows. In Sect. 2, we motivate and prove Theorem 1.1, our lower bound on the online Ramsey number, via the method of conditional expectations. In Sect. 3, we prove the lower bound Theorem 1.4 for \(\tilde{r}(3,n)\) using a Painter strategy designed to avoid red triangles. We prove the upper bound Theorem 1.5 in Sect. 4. Then, in Sect. 5, we study the Subgraph Query Problem for its own sake, proving the upper bound in Conjecture 1.9 as well as Theorems 1.10, 1.11, 1.12, 1.13 and 1.15. We include a handful of open problems raised by our research in the closing remarks.
Unless otherwise indicated, all logarithms are base e. For clarity of presentation, we omit floor and ceiling signs when they are not crucial. We also do not attempt to optimize constant factors in the proofs.
2 General Lower Bounds
2.1 Motivation
In this section, we prove Theorem 1.1 via a weighting argument, motivated by the method of conditional expectations and a result of Alon [2] on the maximum number of copies of a given graph H in a graph with a fixed number of edges.
The first idea, the derandomization technique known as the method of conditional expectations (see Alon and Spencer [3]), can be used to give the following “deterministic” proof of the classical lower bound on diagonal Ramsey numbers. We will show that
Suppose that for some N,
Paint the edges of \(K_{N}\) one at a time as follows. To each vertex subset U of order n, assign a weight w(U) which is the probability that U becomes a monochromatic clique if the edges which remain uncolored at that time are colored uniformly at randomly. That is, writing e(U) for the number of edges already colored in U,
At every step, the total weight \(\sum _{U}w(U)\) is equal to the expected number of monochromatic cliques if the remaining edges are painted uniformly at random. It is therefore possible to paint each edge so as not to increase the total weight. Since the condition \(\sum _{U}w(U)<1\) is initially guaranteed by (2), we can maintain this condition throughout the course of the game, ending with a coloring where there is no monochromatic clique of order n.
We now wish to apply such a weighting argument to the online Ramsey game. The key observation is that if \(\tilde{r}(n, n)\) is close to r(n, n), then, since the graph built by Builder has at least r(n, n) vertices, it must be extremely sparse. In particular, most of the weight should be concentrated on sets U almost none of whose edges are ever built.
This is where the idea behind Alon’s result [2] comes in. For any fixed graph H, that paper solves the problem of determining the maximum possible number of copies of H in a graph with a prescribed number of edges. Roughly speaking, Alon showed that the maximum number of copies of H can be controlled by the size of the maximum matching in H. We show that this heuristic also applies to the online Ramsey game, though it will be more convenient for our calculations to work with minimum vertex covers instead of maximum matchings.
To make this idea work, instead of controlling the total weight function \(\sum _{U}w(U)\), we restrict the sum to subsets U with a large minimum vertex cover, which are comparatively few in number. Even if the total weight \(\sum _{U}w(U)\) becomes large, the amount of weight supported on sets U with a large vertex cover is much smaller, and this is the only weight that stands a chance to make it to the finish line and complete a monochromatic clique.
2.2 The Proof
Using the weighting argument described informally above, we now prove a lower bound on the value of \(\tilde{r}(m,n;p)\), where Painter plays randomly, independently coloring each edge red with probability p and blue with probability \(1-p\).
Theorem 2.1
If, for some \(m,n,N\ge 1\) and \(p\in (0,1)\), there exist \(c\le \frac{1}{2}m\) and \(d\le \frac{1}{2}n\) for which
then \(\tilde{r}(m,n;p)>N\).
We would like to show that regardless of Builder’s strategy, the online random Ramsey game lasts for more than N steps with probability at least 1/2.
Suppose the game ends in at most N turns and, without loss of generality, is played on 2N vertices. Let \(G_{t}\), for \(0\le t\le N\), be the state of the graph after t turns. Assign to each subset \(U\subset V(G)\) an evolving weight function
The value of w(U, t) is the probability that U becomes a red clique if the remaining edges are built.
We say that \(C \subset V(G)\) is a vertex cover of G if every edge is incident to some vertex \(v \in C\). If \(U\subset V(G)\), let c(U, t) be the size of the minimum vertex cover of \(G_{t}[U]\). Note that c(U, t) is a nondecreasing function of t. For each pair (k, c) with \(k \ge 2c\), we will be interested in the total weight supported on sets of order k with \(c(U,t) \ge c\),
Since w(U, N) is nonnegative and \(w(U,N)=1\) if and only if U is a red clique, we see that for all \(c \le m/2\), \(w_{m,c}(N)\) is an upper bound for the number of red copies of \(K_m\) built after N turns. We would like to upper bound the expected value of \(w_{m,c}(N)\).
Lemma 2.2
With \(w_{m,c}(t)\) as above, regardless of Builder’s strategy,
Proof
Each U with the property \(c(U,N)\ge c\) first achieves this property at a time \(t_{c}(U)\). We say that U is c-critical at this time. Write
to be the contribution of the c-critical sets U to \(w_{k,c}(t)\). Crucially, if we focus on the family of U for which \(t_{c}(U)=t\), their expected total weight will remain \(w_{k,c}^{*}(t)\) indefinitely. Thus,
Now, a set U which is c-critical at time t must be the vertex-disjoint union of the edge \(e_{t}\) that Builder builds at time t and a set \(U'\) of size \(k-2\) with a vertex cover of order \(c-1\). Also, because U has a vertex cover of order \(c-1\) before adding this edge \(e_{t}\), the edges incident to \(e_{t}\) must also be incident to one of the \(c-1\) vertices in the vertex cover of \(U'\), so \(e_{t}\) is incident to a total of at most \(2c-2\) edges in U. It follows that after turn \(t=t_{c}(U),\)
where in particular if \(U'\) is already not monochromatic then neither is U. The exponent comes from the fact that among the total \(2(k-2)\) edges between \(e_{t}\) and \(U'\) at least \(2(k-2)-2(c-1)=2k-2c-2\) are thus far unbuilt and still contribute factors of p to the weight of w(U, t). Thus, since each \(U'\) completes at most one set U which is c-critical at time t,
Further, note that there can only be c-critical sets at time t if \(e_t\) is colored red, which occurs with probability p. Otherwise, \(w_{k,c}^{*}(t) = 0\). Taking expectations and using the fact that \(\mathbb {E}w_{k,m}(t)\) is nondecreasing in t gives
Summing over all t,
Iterating this last inequality, we conclude that
as desired. \(\square \)
The same analysis with the blue weight function
leads to the conclusion that \(\mathbb {E}w'_{n,d}(N)\le (1-p)^{\left( {\begin{array}{c}n\\ 2\end{array}}\right) -d(d-1)}(2N)^{n-d}\) for all \(n \ge 2d\). The assumption of Theorem 2.1 then implies that the expected number of red \(K_m\) plus the expected number of blue \(K_n\) is at most 1/2. This implies that the probability of containing either is at most 1/2, completing the proof of Theorem 2.1. Theorem 1.1 follows as an immediate corollary.
3 Lower Bound via Alterations
In this section, we improve the lower bound for the off-diagonal online Ramsey numbers \(\tilde{r}(3,n)\) using a different Painter strategy. Our proof extends an alteration argument of Erdős [12] which shows that
for some constant \(c>0\). The main idea of Erdős’ proof was to show that in a random graph G(r, p) with \(p\approx r^{-1/2}\), only a small fraction of the edges need to be removed to destroy all triangles. Moreover, with high probability, removing these edges doesn’t significantly affect the graph’s independence number.
Our proof involves a randomized strategy which pays particular attention to avoiding red triangles. Instead of painting entirely randomly, Painter’s strategy is modified in two ways to avoid creating red triangles. First, if an edge is built incident to a vertex of degree less than \((n-1)/4\), Painter always paints it blue. Second, if painting an edge red would create a red triangle, Painter again always paints it blue. In all other cases, Painter paints edges red with probability p and blue with probability \(1-p\).
In order to show that this Painter strategy works, we first prove a structural result about Erdős–Rényi random graphs. Roughly speaking, this lemma implies that if an edge is removed from each triangle in G(r, p), the remaining graph still has small independence number.
Lemma 3.1
Suppose n is sufficiently large, \(p = 20 \log n / n\), \(r = 10^{-6} n^2 /(\log n)^2\) and \(G \sim G(r,p)\) is an Erdős–Rényi random graph. Then, with high probability, there does not exist a set \(S\subset V(G)\) of order n such that more than \(\frac{n^2}{10}\) pairs of vertices in S have a common neighbor outside S.
Proof
Let \(E_1\) be the event that the maximum degree of G is at most 2rp. For a given vertex subset S of order n, let \(E_1(S)\) be the event that every vertex outside S has at most 2rp neighbors in S. Thus, \(E_1\) implies \(E_1(S)\) for all S.
For a set S of size n, let \(E_2(S)\) be the event that at most \(\frac{n^2}{10}\) pairs of vertices in S have a common neighbor outside S and let \(E_2\) be the event that \(E_2(S)\) holds for all S. We will show \(E_1 \wedge E_2\) occurs w.h.p. which in turn implies that \(E_2\) itself occurs w.h.p.
The distribution of \(\deg (v)\) for a single vertex \(v\in G\) is the binomial distribution \(B(r-1,p)\). Using the Chernoff bound (see, e.g., Appendix A in [3]), we find that
Taking the union over all vertices of G, it follows that
so \(E_1\) occurs w.h.p.
Fix a set S of n vertices. For \(v \in V(G) \backslash S\), define \(\deg _S(v)\) to be the number of neighbors of v in S. Since \(E_1\) implies \(E_1(S)\), we have
We will show that this last probability is so small that we may union bound over all S.
For \(E_1(S)\) to occur, the possible values of \(\deg _S(v)\) range through [0, 2rp]. We will cut off the bottom of this range and divide the rest into dyadic intervals. Let \(D_0 = -1, D_1 = 4enp, D_2 = 8enp, D_3 = 16enp, \ldots , D_k = 2rp\) so that \(D_i = 2D_{i-1}\) for each \(2\le i \le k-1\) and \(D_k \le 2D_{k-1}\). The number of intervals k satisfies \(k\le \log _2(r/n) \le 2\log n\).
Define \(d_i\) to be the number of \(v \in V(G) \backslash S\) satisfying \(D_{i-1} < \deg _{S}(v) \le D_i\). For \(\overline{E_2 (S)}\) to occur, it must be the case that
as the left hand side counts each pair in S with a common neighbor outside S at least once. In particular,
Notice that since \(D_1 = 4enp = 80e\log n\) and \(d_1 \le r\),
so at least half the contribution of (3) must come from \(i\ge 2\). Thus,
We would like to bound the probability that \(E_1(S)\) and (4) occur simultaneously. Let T be the family of all sequences \((d_i)_{i=1}^k\) which sum to \(r-n\) and satisfy (4). Given the choice of \((d_i)_{i=1}^k\), the number of ways to assign vertices to dyadic intervals \((D_{i-1},D_i]\) is at most \(\left( {\begin{array}{c}r-n\\ d_1,d_2,\ldots , d_k\end{array}}\right) \).
If \(i\ge 2\) and a vertex v is assigned to \((D_{i-1},D_i]\), the probability that \(\deg _S(v)\) lies in that interval is at most
If \(i = 1\), then we simply use the trivial bound \(\Pr [\deg _S(v) \in (D_0, D_1]] \le 1\). Thus,
where we used \(\left( {\begin{array}{c}r-n\\ d_1, d_2,\ldots , d_k\end{array}}\right) < r^{d_2 + \cdots + d_k}\). Next, the number of compositions of \(r-n\) into k parts is at most \(r^k\), so \(|T| \le r^k\) and we have
where
It remains to maximize the exponent in (5) subject to (4). Consider the function
Notice that \(D_1 = 4enp = 80e\log n\) so that for \(D\ge D_1\),
Thus, f(D) takes negative values on \([D_1, D_k]\). Its derivative is
Since \(r \le n^2\), we find that whenever \(D \ge D_1 = 4enp = 80e\log n\),
and so f(D) is monotonically increasing on \([D_1, D_k]\) and attains its maximum value at \(D_k = 2rp\). With \(2rp = 4\cdot 10^{-5} n/\log n\) and n sufficiently large, observe that
so that this maximum value is
In particular, because \(\left( {\begin{array}{c}D\\ 2\end{array}}\right) \ge D^2/3\) for \(D \ge 3\) and f(D) is always negative,
for any \((d_i)\in T\).
Returning to (5), it follows that
There are at most \(\left( {\begin{array}{c}r\\ n\end{array}}\right) \le e^{2n\log n}\) subsets S of size n to consider and \(r^k \le r^n \le e^{2n \log n}\) as well, so
Both summands on the right vanish rapidly, so \(E_2\) holds w.h.p., as desired. \(\square \)
With this lemma in hand, we are now ready to prove Theorem 1.4.
Proof of Theorem 3.2
Let \(p = 20 \log n / n\), \(r = 10^{-6} n^2/(\log n)^2\) and \(N=\frac{(n-1)r}{8}\).
We will give a randomized strategy for Painter such that, regardless of Builder’s strategy, after N edges are colored there is neither a red \(K_3\) nor a blue \(K_n\) w.h.p. Thus, there exists a strategy for Painter which makes the game last more than N steps and the desired bound \(\tilde{r}(3,n)>N\) follows. Note that proving the result with positive probability suffices, but our argument shows it w.h.p. for no additional cost.
We now describe Painter’s strategy. Initially, all vertices are considered inactive; a vertex is activated when its degree reaches at least \((n-1)/4\). The active vertices are labeled with the natural numbers in [r] when they reach degree at least \((n-1)/4\), using an arbitrary underlying order on the vertices to break ties. Since \(N = (n-1)r/8\), there will never be more than r active vertices.
When Builder builds an edge (u, v), this edge is considered inactive if either u or v is inactive immediately after (u, v) is built and active otherwise. The status of an edge remains fixed once it is built, so that inactive edges remain inactive even if both of its incident vertices are active at a later turn. Painter automatically colors inactive edges blue.
If Builder builds an active edge (u, v), Painter first checks if u and v have a common neighbor w such that (u, w) and (v, w) are both red. For brevity’s sake, we call such a vertex w a red common neighbor of u and v. If so, Painter paints (u, v) blue so as to not build a red triangle and we call such an edge altered. Otherwise, Painter paints it red with probability p and blue with probability \(1-p\). Following this strategy, Painter guarantees that no red triangles are built. It suffices to show that w.h.p. no blue \(K_n\) is built either.
Here is an equivalent formulation of Painter’s strategy. At the start of the game, Painter samples an Erdős–Rényi graph \(G = G([r],p)\) on the labels which he keeps hidden from Builder. Inactive edges are painted blue. When an active edge between vertices labelled i and j is built, it is painted red if and only if \(i\sim j\) in G and these two vertices currently have no red common neighbor.
Now, we apply Lemma 3.1 to the graph G. Letting \(E_2(S)\) be the event that an n-set S has at most \(n^2/10\) pairs with outside common neighbors and \(E_2 = \bigwedge _S E_2(S)\), we see that \(\Pr [\overline{E_2}] \rightarrow 0\) as \(n\rightarrow \infty \).
For a set \(S\subseteq [r]\) of labels, write T(S) for the set of active vertices with labels in S. We seek to bound the probability of the event B(T(S)) that T(S) is a blue n-clique at the end of the game. Because any blue n-clique would have all of its vertices active (as each vertex of the n-clique would have degree at least \(n-1\ge (n-1)/4\)), if none of the events B(T(S)) occurs, then no blue \(K_n\) is ever built. Once we show that the probability of a single B(T(S)) is sufficiently small, we will apply the union bound over all S to show that w.h.p. no blue \(K_n\) is built.
First, note that if any edge (u, v) in T(S) is altered (and hence blue), we may assume that their red common neighbors lie outside T(S). Otherwise, there must be two red edges inside T(S) already and T(S) can never become a blue n-clique.
With this in mind, conditioning on the event \(E_2(S)\), at most \(n^2/10\) altered blue edges are built in T(S). Within T(S) there can be at most \(n^2/4\) inactive edges. Assuming B(T(S)) occurs, there are at least
edges between vertices of T(S) that are both active and unaltered. For B(T(S)) to occur, each of these active and unaltered edges would have to be colored blue on its turn. On the other hand, each of these edges has a chance p of being colored red on that turn.
Thus, we find that
with one factor of \(1-p\) for each unaltered active edge built in T(S). Thus,
The second summand goes to zero, so it suffices to show the first does as well. We have
Using \(1-p \le e^{-p}\), the right-hand side is at most
also tending to zero as \(n\rightarrow \infty \). Thus, the probability that either \(\overline{E_2}\) or some B(T(S)) occurs tends to zero. Therefore, with high probability no blue \(K_n\) is built.
4 Off-Diagonal Upper Bounds
In Sect. 2, we proved lower bounds of the form \(\tilde{r}(m,n)\ge \Omega (n^{(2-\sqrt{2})m+o(m)})\) on the off-diagonal online Ramsey numbers through an analysis of the online random Ramsey number. It is easy to give an upper bound of the form \(\tilde{r}(m,n) \le O(n^{2m-2})\) simply by applying the Erdős–Szekeres bound for classical Ramsey numbers and the trivial observation that \(\tilde{r}(m,n)\le \left( {\begin{array}{c}r(m,n)\\ 2\end{array}}\right) \).
However, the simple inductive proof of the Erdős–Szekeres bound suggests a Builder strategy that does considerably better. Namely, build many edges from one vertex until it has a large number of edges of one color, then proceed inductively in that neighborhood. This strategy is particularly well suited to the online Ramsey game because the number of edges built is only slightly more than linear in the number of vertices used, allowing us to derive a bound of the form \(\tilde{r}(m,n)\le O(n^{m})\).
A slight variation on this argument allows us to bound the online Ramsey number in terms of the bounds for classical Ramsey numbers.
Lemma 4.1
Let \(m \le n\) be positive integers with m fixed. Let \(m_0=\lfloor m/2 \rfloor + 1\) and \(n_0=\lfloor \sqrt{n} \rfloor \). Suppose \(\mathcal {L}\) is a positive real such that for all \(m_0 \le m' \le m\) and \(n_0 \le n' \le n\),
Then
for a constant \(C_m\) depending only on m.
Proof
We describe a general Builder strategy for the online Ramsey game with parameters m and n and some savings parameter \(\mathcal {L}\). Let \(f(m,n)=\frac{1}{\mathcal {L}}\left( {\begin{array}{c}m+n-2\\ m-1\end{array}}\right) \), so we have \(f(m-1,n)+f(m,n-1)=f(m,n)\) by Pascal’s identity.
Begin by building \(f(m,n) - 1\) edges out of a given initial vertex \(v_{1}\). If \(f(m-1,n)\) of these edges are colored red, we proceed to the red neighborhood of \(v_1\); otherwise, we proceed to the at least \(f(m,n-1)\) vertices in the blue neighborhood of \(v_1\). If at some step we reach a neighborhood with \(f(m - i, n - j)\) vertices, we build \(f(m - i, n -j) - 1\) edges inside this neighborhood from one of the vertices, which we label \(v_{i+j+1}\). If \(f(m - i - 1, n - j)\) of these edges are colored red, we proceed to the red neighborhood of \(v_{i+j+1}\); otherwise, we proceed to the at least \(f(m-i,n-j-1)\) vertices in the blue neighborhood of \(v_{i+j+1}\). We stop once m reaches \(m_0\) or n reaches \(n_0\), ending up with either \(f(m_{0},n')\) vertices for some \(n_{0}\le n'\le n\) or \(f(m',n_{0})\) vertices for some \(m_{0}\le m'\le m\). Once we reach this stage, we build all edges in the remaining set.
Suppose now that we arrive at a set S of order \(f(m_0, n')\). By construction, there are \(\ell = m + n - m_0 - n'\) vertices \(v_1, \dots , v_\ell \) such that \(m-m_0\) of the vertices \(v_i\) are joined in red to every \(v_j\) with \(j > i\) and every \(w \in S\). The remaining \(n - n'\) vertices \(v_i\) are joined in blue to every \(v_j\) with \(j > i\) and every \(w \in S\). But since
the complete graph on S contains either a red \(K_{m_0}\) or a blue \(K_{n'}\), either of which can be completed to a red \(K_m\) or a blue \(K_n\) by using the appropriate subset of \(v_1, \dots , v_\ell \). If we had instead arrived at a set of order \(f(m',n_0)\), a similar analysis would have applied.
Note that the total number of edges built in the branching phase is at most \((m+n)f(m,n)\), while the number built by filling in the final clique is at most \( \max (f(m_{0},n)^{2}, f(m,n_{0})^{2})\). Using the choice of \(m_0\) and \(n_0\), the total number of edges built is easily seen to be at most a constant in m times the previous expression. \(\square \)
From here we derive Theorem 1.5.
Proof of Theorem 4.2
We apply the bound
due to Ajtai, Komlós and Szemerédi [1]. In particular, suppose \(m_0=\lfloor m/2 \rfloor + 1\), \(n_0=\lfloor \sqrt{n} \rfloor \) and \(m', n'\) satisfy \(m_0 \le m' \le m\) and \(n_0 \le n' \le n\). Then, for some constants \(C, C' >0\) depending only on m, we have
and
verifying the conditions of Lemma 4.1 with \(\mathcal {L} = \Omega _m(\log ^{\lfloor m/2 \rfloor - 1} n)\). It follows by that lemma that there exists another constant \(C''>0\) depending only on m for which
Fixing \(m\ge 3\) and taking \(n\rightarrow \infty \), this implies
as desired. \(\square \)
We remark that while the statement and proof of Lemma 4.1 are designed for the case where m is a constant, they can be easily modified to make them meaningful for all m and n.
5 The Subgraph Query Problem
The vertex cover argument in Sect. 2 was motivated by our study of the closely-related Subgraph Query Problem. Indeed, one can view this problem as an instance of the online Ramsey game with a random Painter where Builder single-mindedly tries to build a clique in one color, ignoring the other color entirely.
Let \(p\in (0,1)\) be the probability that Builder successfully builds any given edge in the Subgraph Query Problem. We are primarily interested in the quantity f(H, p), which we defined as the minimum N for which there exists a Builder strategy which builds a copy of H with probability at least \(\frac{1}{2}\) in N turns. Of secondary interest is the quantity t(H, p, N), which we define as the maximum, over all Builder strategies, of the expected number of copies of H that can be built in N turns. It is easy to see that
Thus, upper bounds on t(H, p, N) yield lower bounds on f(H, p).
5.1 Connection with Online Ramsey Numbers
We first check that the Subgraph Query Problem gets easier when edges are built with higher probability.
Lemma 5.1
For any \(m\ge 3\), \(f(K_m,p)\) is a nonincreasing function of \(p\in (0,1)\).
Proof
Suppose \(p < q\) and \(f(K_m, p) = N\). This means that in the Subgraph Query Problem with parameter p, Builder has an N-move strategy S to win with probability at least half. Strategy S is defined by Builder’s choice of edge to build at each step, given the data of which edges were successfully built in previous steps.
Builder’s strategy for the Subgraph Query Problem with parameter q is as follows. For each edge that Builder successfully builds, Builder then flips a biased coin that comes up heads \(\frac{p}{q}\) of the time. If the coin comes up tails, Builder pretends the edge actually failed to build, and acts according to strategy S with respect to only the edges for which the coin came up heads. Just looking at the edges which come up heads, Builder is exactly following strategy S, and so builds a \(K_m\) with probability at least 1/2 in N steps. \(\square \)
We now prove Theorem 1.10, which connects the Subgraph Query Problem to the online Ramsey game. Recall the statement:
Proof of Theorem 5.2
We first show the left side of the inequality. Let \(N=\min \{f(K_m, p), f(K_n,1-p)\}\) and suppose that \(f(K_m,p)\) is the smaller of the two. Then there exists an N-move Builder strategy which builds a \(K_m\) with probability at least half. Now, let Builder play the online Ramsey game against a random Painter with the same probability parameter p. Builder’s strategy will be to treat red edges as successfully built and blue edges as failed. In this way, Builder wins the online Ramsey game in N moves with probability at least half, by constructing a red \(K_m\). Similarly, if \(f(K_n, 1-p)\) were smaller, Builder would instead treat blue edges as successfully built and red edges as failed. This would then guarantee the construction of a blue \(K_n\) with probability at least half.
Now we show the right side of the inequality. Suppose \(N=\tilde{r}(m,n;p)\), so in the online Ramsey game against random Painter with parameter p, there exists an N-move Builder strategy which builds a red \(K_m\) or blue \(K_n\) with probability at least half. In particular, this same strategy guarantees either a red \(K_m\) with probability at least \(\frac{1}{4}\) or a blue \(K_n\) with probability at least \(\frac{1}{4}\).
Suppose the first is true. Then Builder plays the Subgraph Query Game using this same strategy, treating red edges as successfully built and blue as failed. In N moves, he has at least a \(\frac{1}{4}\) chance of successfully building a \(K_m\). Repeating this strategy three independent times on three different vertex sets, Builder uses 3N moves to build a \(K_m\) with probability at least
showing that \(f(K_m,p) \le 3\tilde{r}(m,n;p)\) in this case. Similarly, if the second case occurs, \(f(K_n,1-p) \le 3\tilde{r}(m,n;p)\). Either way, the smaller of \(f(K_m,p)\) and \(f(K_n, 1-p)\) is bounded above by \(3\tilde{r}(m,n;p)\).
Now we show that Conjecture 1.9 about the Subgraph Query Problem directly implies Conjecture 1.7 about online random Ramsey numbers.
Proof that Conjecture 1.9 implies Conjecture 1.7. Assume Conjecture 1.9, i.e., \(f(K_m, p) = 2^{o(m)}p^{-\frac{2}{3} m + c_m}\) for all \(m\ge 3\), \(p\in (0,1)\). By Theorem 1.10, we have
In the diagonal case of the online Ramsey game, (6) together with Lemma 5.1 implies that \(p=\frac{1}{2}\) gives the online random Ramsey number to within a constant factor. Thus,
This proves part (a).
In the off-diagonal case, a value of p nearly optimizing the right hand side of (6) satisfies \(p = \Theta (\frac{m}{n}\log {\frac{n}{m}})\) by Theorem 1.11, which is proved in Sect. 5.3. Plugging in this value of p, we get
which implies case (b) of Conjecture 1.7. \(\square \)
5.2 The Branch and Fill Strategy
We now prove the upper bound in Conjecture 1.9.
We will say it is possible to build a graph H in O(T) turns, where \(T=T(p)\) is a function of p, if for any \(p\in (0,1)\) it is possible, in the Subgraph Query Game played with probability p, to build a copy of H in O(T) time with probability at least \(\frac{1}{2}\). It is a simple fact about randomized algorithms that if one can achieve any constant success probability in O(T) time then one can iterate the algorithm to succeed with probability \(1-\varepsilon \) in \(O(T \log {\varepsilon ^{-1}})\) time.
We describe a Builder strategy to prove the upper bound in Conjecture 1.9 and conjecture that this is essentially the optimal strategy for the Subgraph Query Problem for cliques.
Lemma 5.3
Let \(a\ge 1\), \(b \ge 2\) and \(n=a+b+1\) satisfy \(2a+3-b\ge 0\). Then
where \(\alpha = \min (1, \frac{b(2a+3-b)}{2(b-1)})\).
Proof
To build a clique \(K_{n}\) in O(T) turns, where \(T = p^{-\frac{2a+b+1}{2}+\frac{\alpha }{b}}\), we follow a strategy with three phases:
-
1.
Build a clique U on a vertices. By induction, the number of turns needed will be negligible.
-
2.
Find \(p^{a}T\) common neighbors of U in \(O_n(T)\) time with high probability. This is done by repeatedly picking a new vertex v and trying to build each of the edges between v and the vertices in U until one fails. Let W be the set of common neighbors found in this way.
-
3.
Among the vertices of W, pick a vertex \(w_{1}\) and try to build all edges incident to \(w_{1}\) within W. Let \(W_{1}=N(w_{1})\cap W\) be the neighborhood determined. Try to build all \(\left( {\begin{array}{c}|W_{1}|\\ 2\end{array}}\right) \) edges within \(W_{1}\). Remove \(\{w_{1}\}\cup W_{1}\) from W and repeat a total of \(p^{-\alpha }\) times, picking \(w_{2},\ldots ,w_{p^{-\alpha }}\), finding their neighborhoods, and filling them in. Here, \(\alpha \in [0,1]\) is a parameter which we have not yet specified.
After the process is complete, if any one of the \(W_{i}\) contains a b-clique \(W_{i}'\), then we are done, since \(U\cup \{w_{i}\}\cup W_{i}'\) forms an n-clique.
It remains to determine the success probability and the number of steps taken in the above process. By the standard Chernoff bounds, the sizes of all the sets \(W_{i}\) concentrate around their means with high probability. Hence, with high probability,
A standard application of Janson’s inequality (see Chaps. 8 and 10 of [3]) then implies
If i ranges up to \(p^{-\alpha }\) and \(\alpha \le 1\), then the decay factor \((1-p)^{(i-1)b}\) is \(\Theta _{b}(1)\) and can be safely ignored. Since the event that each \(W_{i}\) contains a b-clique is independent of all the others, we need only pick \(p,T,\alpha \) for which the expression \(p^{-\alpha }p^{(a+1)b+\left( {\begin{array}{c}b\\ 2\end{array}}\right) }T^{b}\) is a positive constant. If this is the case, then with at least constant probability our strategy constructs an n-clique.
We also need to know that the total number of turns taken is \(O_n(T)\). This is true in Phases 1 and 2 by design. With high probability, the number of turns taken in filling out each \(W_i\) is \(O_a(p^{a}T+p^{2(a+1)}T^{2})\). Since this is repeated \(p^{-\alpha }\) times, it suffices to have
for the number of turns to be O(T). It remains to optimize the value of T subject to the constraints \(T = O_a(p^{\alpha -2(a+1)})\) and \(p^{-\alpha }p^{(a+1)b+\left( {\begin{array}{c}b\\ 2\end{array}}\right) }T^{b} = \Omega _b(1)\). As long as \(2a + 3 - b \ge 0\), this system has solutions. Solving for \(\alpha \) which minimizes T, we find that any
works, as long as the decay condition \(\alpha \le 1\) was also satisfied. \(\square \)
Lemma 5.3 provides upper bounds for \(f(K_m,p)\) for all \(m\ge 4\), where the shape of the power of p depends on the residue class of m modulo 3.
Theorem 5.4
If \(p\in (0,1)\), then \(f(K_3,p) = O(p^{-3/2})\) and, for \(m\ge 4\),
where
Proof
For \(m = 3\), the bound is simple. Query \(\Theta (p^{-3/2})\) pairs containing a given vertex \(v_1\) and then, among the \(\Theta (p^{-1/2})\) neighbors successfully found, query all pairs. For sufficiently large implied constants, the probability that we build a triangle containing \(v_1\) is at least 1/2.
When \(m\ge 4\), we use Lemma 5.3, taking
This gives the required result. \(\square \)
We conjecture that the bounds in Theorem 5.4 are best possible up to the constant factor. In the next two subsections, we prove this is the case for \(m\le 5\).
5.3 Recursive Graph Building
Recall that f(H, p) is the number of queries needed in the Subgraph Query Problem to build a copy of H with probability at least \(\frac{1}{2}\). When \(H=K_m\), we can prove a lower bound on f(H, p) by combining Theorem 1.10 with Theorem 2.1.
Proposition 5.5
If \(m\ge 3\) and \(c\le \frac{1}{2}m\), then
Proof
Take \(N = \frac{1}{4} p^{-(\left( {\begin{array}{c}m\\ 2\end{array}}\right) - c(c-1))/(m-c)}\), which is chosen so that
Since \((1-p)^{\left( {\begin{array}{c}n\\ 2\end{array}}\right) }(2N)^n\rightarrow 0\) as \(n\rightarrow \infty \), there is some n sufficiently large for which
With \(d=0\), this choice of m, n, N, p, c, d satisfies the conditions of Theorem 2.1, so \(\tilde{r}(m,n;p) > N\). By Theorem 1.10, \(f(K_m,p) \ge \tilde{r}(m,n;p)\), giving the required result. \(\square \)
We now describe a general method for obtaining a similar lower bound on f(H, p) when H is not a clique. As before, define t(H, p, N) to be the maximum expected number of copies of H that can be constructed in N queries. The main result of this section bounds t(H, p, N) when H contains a large matching. To this end, recall that a graph has a k-matching if it contains k disjoint edges.
Theorem 5.6
Let H be a graph containing a k-matching. Then there exists an absolute constant \(A>1\) for which
whenever \(pN \ge 1\).
For any edge \(e\in H\), write \(H\backslash e\) for the graph formed by removing the edge e from H. If U is a subset of the vertices of H, write \(H\backslash U\) for the induced subgraph of H on the complement of U. We begin by proving the following pair of recursive bounds on t(H, p, N).
Lemma 5.7
If H is a simple labeled graph, then
and
where the o(1) term tends to 0 as \(pN \rightarrow \infty \).
Proof
Suppose Builder follows an optimal strategy which achieves t(H, p, N) expected copies of H in N turns. For each copy \(H_{i}\) of H that appears during the game, distinguish the edge \(e_{i}\) which is built last in \(H_{i}\). For each \(e\in E(H)\), let \(t_{e}(H,p,N)\) be the maximum expected number of copies of H that Builder can build, only counting those copies of H in which e is the last edge built. Then, clearly,
Furthermore, \(t_{e}(H,p,N)\le p t(H\backslash e,p,N)\), since each copy of \(H\backslash e\) can become exactly one copy of H with success rate p if e is built. Inequality (7) follows.
As for recursion (8), note simply that the number of copies of H is bounded by the number of choices for the images of the vertices u, v which are connected by an edge times the number of copies of \(H\backslash \{u,v\}\). By the Chernoff bound, the number of choices of an edge is tightly concentrated around pN, so the inequality follows. \(\square \)
It remains to apply these inequalities recursively.
Proof of Theorem 5.8
By (8), there is an absolute constant \(A > 1\) for which
whenever \(pN \ge 1\).
We proceed by induction on the number of edges in H. When H is an empty graph on m vertices, the result is trivial with \(k=0\). Let H be a labeled graph for which the induction hypothesis is true for every graph with fewer edges than H. Let \(e\in E(H)\) run over all edges of H. We break into two cases:
Case 1. Every \(H\backslash e\) contains a k-matching. Then, by induction and (7), it follows that
as desired.
Case 2. There exists \(e\in E(H)\) for which \(H\backslash e\) contains no k-matching. Then, let \(e_{2},\ldots ,e_{k}\) be \(k-1\) edges which complete a k-matching of H containing e. The edges incident to e must all be incident to one of the \(e_{i}\) or else \(H\backslash e\) would contain a k-matching. Also, e cannot form a 4-cycle with any \(e_{i}\) for the same reason. From these two facts one finds that e can be incident to at most \(2(k-1)\) other edges in total. Let \(H'\) be the graph obtained from H by removing the two vertices of e from H. Applying the induction hypothesis on \(H'\), which is a graph on \(v(H)-2\) vertices with at least \(e(H)-(2k-1)\) edges and a \((k-1)\)-matching, we find that
Combining this with inequality (9), we have
as desired.
For our purposes, we will always assume \(pN \ge 1\). Otherwise, with high probability at most a constant number of edges are built successfully in the Subgraph Query Game, so t(H, p, N) will be negligibly small.
Since \(t(H,p,N) < 1/2\) implies \(f(H,p) > N\), Theorem 5.6 immediately implies Theorem 1.12. Comparing this with Proposition 5.5, we note that while Theorem 1.12 gives a bound for all graphs H, it gives an inferior quantitative dependence on e(H). While this stronger quantitative dependence in Proposition 5.5 seems to be only a minor benefit, it was needed in the proof of Theorem 1.11, which is why we retained the proof.
For large m, this bound only gives Corollary 1.14, that
which is still far from the conjectured growth rate \(p^{-\frac{2}{3}m+O(1)}\). However, for \(m \le 5\), Theorem 1.12 can be used to pin down the asymptotic growth rate of \(f(K_m, p)\), proving Theorem 1.13.
Proof of Theorem 5.9
The upper bounds for these cases are proved in Sect. 5.2. Apply Theorem 1.12 by taking \(k=1\) for \(m=3\) and \(k=2\) for \(m=4, 5\) to get the desired lower bounds. \(\square \)
When \(m\ge 6\), the matching argument of Theorem 5.6 does not seem sufficient for determining the exact growth rate of \(f(K_m, p)\). Indeed, we will now exhibit an infinite family of graphs for which Theorem 5.6 is tight.
For \(k\ge 1\), let \(H_k\) be the graph on 2k vertices \(a_i, b_i\), \(1\le i \le k\), such that \(a_i \sim a_j\) for all \(i\ne j\), \(b_i \not \sim b_j\) for all \(i \ne j\), and \(a_i \sim b_j\) if and only if \(i\le j\). Thus \(H_k\) is a split graph consisting of a k-clique, a k-independent set, and a half graph between them. We show that Theorem 5.6 is tight for \(H_k\) up to a constant factor.
Note that the construction below requires N to grow like a tower of \(p^{-1}\)’s of height k. It is possible that the same lower bound is false in the regime \(N \le p^{-C}\) for any \(C = C(k) > 0\).
Theorem 5.10
For every \(k\ge 1\), the graph \(H_k\) defined above contains a k-matching and, for any \(p\in (0,1)\),
provided N is sufficiently large in terms of p.
Proof
In fact, \(H_k\) has \(k^2\) edges, 2k vertices, and contains a unique k-matching \({(a_i, b_i)}_{i\le k}\). It will suffice to show that for all \(p\in (0,1)\) and N sufficiently large in terms of p,
Builder’s strategy will involve constructing a nested sequence of vertex sets \(U_{1},U_{2},\ldots ,U_{k}\). The first set \(U_{1}\) is just an arbitrary set of N/k vertices. In each successive \(U_{i}\), assuming \(|U_i| \ge \sqrt{N}\) we can pick \(N_{i}=N/(k|U_{i}|)\) vertices \(a_{i}^{(1)},a_{i}^{(2)},\ldots ,a_{i}^{(N_{i})}\in U_{i}\) and try to build all edges from each \(a_{i}^{(j)}\) to every other vertex in \(U_{i}\). This step takes at most N/k turns. The set \(U_{i+1}\) is then defined to be the common neighborhood of \(a_{i}^{(1)},\ldots ,a_{i}^{(N_{i})}\) within \(U_i\).
Repeating this process k times, we use at most N turns. For N sufficiently large, with high probability the edge density from \(a_{i}^{(1)},a_{i}^{(2)},\ldots ,a_{i}^{(N_{i})}\) to the rest of \(|U_i|\) is \((1+o(1))p\). Thus, the number of copies of \(H_{k}\) built in this way is bounded below by
since we can choose \(a_{i}\) out of any of the \(N_{i}\) vertices \(a_{i}^{(1)},\ldots ,a_{i}^{(N_{i})}\) and \(b_{i}\) out of any of its \((1+o(1))p|U_{i}|\) neighbors. As long as N is large enough that \(|U_{k}|\ge \sqrt{N}\) with high probability, there will be enough vertices in the last set \(U_k\) to perform the strategy. This argument successfully constructs \(\Theta _k(p^kN^k)\) copies of \(H_k\). Taking N to be a tower of \((2+2p^{-1})\)’s of height k is sufficient. \(\square \)
We finish the subsection with an application of the preceding results and prove Theorem 1.11. Recall that this theorem states that for m fixed and \(n\rightarrow \infty \), a value of p for which \(\tilde{r}_{\text { rand}}(m,n) \le 3\tilde{r}(m,n;p)\) satisfies \(p = \Theta (\frac{m}{n}\log {\frac{n}{m}})\).
Proof of Theorem 5.11
By Theorem 5.4,
and in fact it can be checked from the proof that the explicit dependence on m is polynomial. Moreover, using Proposition 5.5 with \(c=0\), we have that
since \(\frac{m-1}{2}\ge \frac{m}{3}\) for \(m\ge 3\). Putting all this together, there exists an absolute constant \(A>0\) for which
for all \(m\ge 3\), \(p\in (0,1)\).
By Theorem 1.10, we have
Pick some \(p_0 \in (0,1)\) which maximizes the function \(\min \{f(K_m, p), f(K_n, 1-p)\}\). Such a \(p_0\) exists because \(f(K_m,p)\) is nonincreasing in p, \(f(K_n,1-p)\) is nondecreasing, and both are integer-valued. Then, \(\tilde{r}_{\text { rand}}(m,n)\le 3\cdot \tilde{r}(m,n;p_0)\). It remains to check that we could have chosen \(p_0 = \Theta (\frac{m}{n}\log {\frac{n}{m}})\). By (10) and the fact that the bounds are continuous, we have
and
Since \(m\ge 3\) is fixed and \(n\rightarrow \infty \), the first inequality implies \(p_0\rightarrow 0\). In particular, \(\log (1-p_0)=-p_0 +O(p_0^2)\). Taking the logarithm of both sides in the inequalities above, we have
and
Taking \(n\rightarrow \infty \) and dividing through by \(mp_0\), these inequalities combine to show
and it follows that \(p_0 = \Theta (\frac{m}{n}\log {\frac{n}{m}})\), as desired. \(\square \)
5.4 The Value of \(t(K_m,p,N)\) for Large N
In this section, we investigate the behavior of the function \(t(K_m,p,N)\) as \(N\rightarrow \infty \). We find that when N is very large, the essentially optimal strategy for building as many copies of \(K_m\) as possible is to fill in the edges of a clique on \(\sqrt{2N}\) vertices. This is in stark contrast with the rather delicate procedure described in Sect. 5.2 to build a single copy of \(K_m\).
5.4.1 Chernoff Bounds and Subjumbledness
We will need a standard lemma (see, for example, [24, Theorem 2.1]) saying that with high probability all moderately large induced subgraphs of a random graph G(N, p) have the expected number of edges. Recall that if \(U\subset V(G)\) is a vertex subset of G, we write G[U] for the induced subgraph on U.
Lemma 5.12
If \(G=G(N,p)\) and \(\varepsilon >0\), then, with high probability,
for all \(|U|=\Omega _{\varepsilon }(p^{-1}\log N)\).
In the literature (see [24] and its references), this pseudorandomness property is usually called jumbledness. We also use this term, though in a slightly different way to how it is usually used.
Definition 5.13
A graph G is \((p,M,\varepsilon )\)-jumbled if, for every \(U\subseteq V(G)\) with \(|U|\ge M\),
A graph G is \((p,M,\varepsilon )\)-subjumbled if it is a subgraph of some \((p,M,\varepsilon )\)-jumbled graph.
In what follows, we will show that subjumbled graphs cannot have too many cliques. For the graph-building problem, the heuristic is that it’s not possible to build more copies of H in a known jumbled graph G with pN queries than it is with N queries in G(N, p).
5.4.2 Degeneracy
Define a graph to be d-degenerate if there exists an ordering of the vertices \(v_{1},\ldots ,v_{n}\) such that \(|N(v_{i})\cap \{v_{1},\ldots ,v_{i-1}\}|\le d\) for all i. The following simple lemma is well known.
Lemma 5.14
Every graph with E edges is \(\sqrt{2E}\)-degenerate.
Proof
We exhibit the degenerate ordering by picking the vertices backwards from \(v_{n}\) to \(v_{1}\). At each step, pick \(v_{i}\) to be the minimal degree vertex in the current graph and delete it. Note that \(d(v_{i})\le i-1\) because there are only i points left and also \(d(v_{i})\le \frac{2E}{i}\) because the sum of the degrees is at most 2E and \(v_{i}\) has minimal degree. It follows that at every step \(d(v_{i})\le \min (i,\frac{2E}{i})\le \sqrt{2E}\), as desired. \(\square \)
This is not quite sufficient for our purposes, but it gives the main idea. What we really need is a better understanding of degeneracy in jumbled graphs. In what follows, given a candidate ordering \(v_{1},\ldots ,v_{n}\) of the vertices, we write \(N^{-}(v_{i})=N(v_{i})\cap \{v_{1},\ldots ,v_{i-1}\}\) and \(d^{-}(v_{i})=|N^{-}(v_{i})|\).
Lemma 5.15
Any \((p,M,\varepsilon )\)-subjumbled graph on N edges is \(\max ((1+\varepsilon )M\sqrt{p},(1+\varepsilon )\sqrt{2pN})\)-degenerate.
Proof
Let H be a graph on N edges that is a subgraph of some \((p,M,\varepsilon )\)-jumbled graph G. We again pick vertices of the graph H in order of increasing degree among the remaining vertices. Let the resulting order be \(v_{1},\ldots ,v_{n}\) and write \(U_{i}=\{v_{1},\ldots ,v_{i}\}\). The construction guarantees that \(v_{i}\) is of minimal degree in \(G[U_{i}]\).
If \(i\le M\), then the subgraph \(H[v_{1},\ldots ,v_{i}]\) has at most as many edges as \(H[v_{1},\ldots ,v_{M}]\), which has at most \((1+\varepsilon )pM^{2}/2\) edges. Thus,
Otherwise, if \(i>M\), the induced subgraph \(H[v_{1},\ldots ,v_{i}]\) has at most \((1+\varepsilon )pi^{2}/2\) edges and it clearly cannot have more than \(e(H)=N\) edges. Because \(v_{i}\) is of minimal degree in this induced subgraph,
and so every vertex has \(d^{-}(v_{i})\le \max ((1+\varepsilon )M\sqrt{p},(1+\varepsilon )\sqrt{2pN})\), as desired. \(\square \)
5.4.3 Counting Cliques
We are ready to prove the following lemma. Recall the standard notation that t(K, H) is the number of labeled graph homomorphisms from K to H. Up to a lower order term, this is the same as counting labeled copies of K in H. In fact, the equality is exact in the case we care about, where K is a clique and H is a simple graph without self-loops.
Lemma 5.16
For all \(p\in (0,1)\), \(m,M\ge 2\) and \(0<\varepsilon <1\), if H is a \((p,M,\varepsilon )\)-subjumbled graph with N edges, then
Proof
Take a degenerate ordering \(v_{1},\ldots ,v_{n}\) of H such that \(v_{i}\) is of minimum degree in \(H[v_{1},\ldots ,v_{i}]\). By Lemma 5.15,
where the second term dominates as soon as \(N\ge M^{2}/2\). Conditioning on whether or not \(v_{n}\) is in the copy of \(K_{m+1}\) we are counting, we see that
In particular, writing \(t(m,N)=\max _{e(H)=N}^{*}t(K_{m},H)\), where the maximum is taken over all graphs H with N edges that are subgraphs of some \((p,M,\varepsilon )\)-jumbled graph, we find that
where \(U(N)=\max ((1+\varepsilon )M\sqrt{p},(1+\varepsilon )\sqrt{2pN})\) and \(e^{+}(d)\) is any upper bound on the number of edges in a graph on d vertices that is a subgraph of a \((p,M,\varepsilon )\)-jumbled graph. The function \(e^{+}\) we take is
To see that \(e^+(d)\) is indeed an upper bound on the number of edges in a graph on d vertices that is a subgraph of a \((p,M,\varepsilon )\)-jumpled graph, we use the trivial bound when d is small, extend to a size M set to use jumbledness when d is somewhat close to M, and use jumbledness directly for d larger than M.
We are left to bound t using the system of inequalities (11). Write
for the approximate optimum value of t(m, N). We induct on m. The base case is \(t(2,N)=2N\). Assume, by induction, that for some \(m\ge 2\),
We would like to show that the same inequality holds for \(m+1\). Iterating (11), there exists a sequence \((d_i)_{i\ge 1}\) of positive integers summing to N for which
and
which implies, by the induction hypothesis, that
Since \(e^+(d)\) is constant on the range \(M\sqrt{p}\le d < M\), the optimal choice of \(d_i\) will never have any points in this range. The main term of (12) can thus be separated into the sum over \(d_i < M\sqrt{p}\) and the sum over \(d_i \ge M\):
Note that \(m\ge 2\), so \(t^*(m,N)\) is a convex nondecreasing function in N. Also, the function \(e^{+}(d)\) is nondecreasing and convex in d except for the jump discontinuity at \(d=M\sqrt{p}\). Therefore, in each of the ranges above, \(t^*(m, \cdot )\) and \(e^+(\cdot )\) are both convex nondecreasing functions.
To bound the first sum in (13), we pass to an integral. Write
Then
Because \(t^*(m,(1+\varepsilon )pd^2/2)/d\) is an increasing function of d and \(d_i \le U(N_{i-1}) = (1+\varepsilon )\sqrt{2pN_{i-1}}\), we have
We had to shift integrals in the second step to guarantee that every value of x in the range of integration is at least \(N_{i-1}\).
Next, \(t^*(m,N)\) is a polynomial in N, so we can absorb the \((1+\varepsilon )\) into the error term. Similarly, we can pull out an error term of \((1+(1+\varepsilon )\sqrt{2p/N})\) from the bounds of the integral to simplify. Reorganizing various error terms, we get
Finally, explicitly evaluating the integral, we have
Estimating the second sum in (13) trivially, we get
To check the error terms in (12) match up is similar: break up each sum into the sums over \(d_i \ge M\) and \(d_i < M\sqrt{p}\). The first sum is estimated by an integral and the second trivially. The result is
which is the right error term for \(t(m+1,N)\), completing the induction. \(\square \)
In particular, and this is essential, the implicit constants in this lemma do not depend on M. As an immediate corollary, we now prove Theorem 1.15. Note that the N above is the number of edges in H, which will correspond to \((1+o(1))pN\) below if N is the number of queries made in the Subgraph Query Game.
Proof of Theorem 5.17
Applying the Chernoff bound from Lemma 5.12, we see that for any \(\varepsilon >0\) we can take some \(M=Cp^{-1}\log N\) so that the random graph G(2N, p) is \((p,M,\varepsilon )\)-jumbled with high probability. Also with high probability, the number of edges built in N queries is \((1+o(1))pN\). It is easy to check that the exponentially small probabilities with which either of these are false have negligible impact on the value of \(t(K_m,p,N)\). The subgraph H built by Builder must therefore satisfy the hypotheses of Lemma 5.16 with \((1+o(1))pN\) edges.
The main term dominates the error terms for N sufficiently large, giving the expected answer which is just \(p^{\left( {\begin{array}{c}m\\ 2\end{array}}\right) }(2N)^{\frac{m}{2}}\), the number of m-cliques in \(G(\sqrt{2N},p)\). This happens once the main term outgrows the largest error term, the term with \(k=m-1\). This happens at \(N = \Omega (p^{-(2m-3)}M^2)\), so it suffices to have \(N \ge \omega (p^{-(2m-1)}\log ^2{(p^{-1})})\). This proves the upper bound in Theorem 1.15. Of course, the lower bound is proved by the strategy of building all edges among \(\sqrt{2N}\) vertices. \(\square \)
6 Concluding Remarks
It is an interesting problem to close the gap in the bounds for the online Ramsey number \(\tilde{r}(m,n)\). In particular, we know that there are positive constants \(c,c'\) for which \(cn^3/(\log n)^2 \le \tilde{r}(3,n) \le c' n^3\) and it seems plausible that these bounds could be brought closer together. Indeed, we conjecture that the lower bound can be improved to \(cn^3/\log n\) by considering the following Painter strategy motivated by the triangle-free process [6]. Painter applies the triangle-free process to obtain an auxiliary triangle-free graph G on vertex set \(\{1, 2, \dots , r\}\) with \(r=c_0 n^2/\log n\). Painter does not reveal this auxiliary graph. As before, we label vertices that reach degree n/4 with \(1,\ldots ,r\) as they arrive at degree n/4. When Builder adds an edge between two vertices in which both vertices have degree at least n/4, then these vertices have labels, say i and j, and Painter paints the edge with the color of the edge ij in G. Otherwise, they color the edge blue. This coloring clearly contains no red triangles, but it remains to show that it contains no blue \(K_n\).
In studying the online Ramsey number, we were usually led by the idea that Builder’s optimal strategy is to fill out an extremely sparse graph on the vertex set they touch. However, if Builder is restricted to play on a small vertex set, this intuition seems to go awry. If we define \(\tilde{r}(m,n;N)\) in the same manner as the online Ramsey number but with the additional restriction that only N vertices are allowed, then we conjecture that the function \(\tilde{r}(m,n;N)\) increases substantially as N decreases from \(2 \tilde{r}(m,n)\), the maximum number of vertices in a graph with \(\tilde{r}(m,n)\) edges, down to its minimal meaningful value r(m, n).
The order of growth of \(f(K_m, p)\) is still open for \(m\ge 6\). In particular, Theorems 1.12 and 5.4 show that \(f(K_6, p) = \Omega (p^{-13/4})\) and \(f(K_6,p) = O(p^{-10/3})\) and we conjecture that the upper bound is correct. This belief is rooted in our conviction that the upper bound for t(H, p, N) given by Theorem 5.6, upon which Theorem 1.12 relies, is not tight when N is on the order of f(H, p). Because of the examples in Theorem 5.10, these upper bounds can be tight when N is very large, so further progress on this problem would need to be more sensitive to the size of N. It is plausible that any advance on this question and its generalizations could also impinge on our estimates for online Ramsey numbers.
References
M. Ajtai, J. Komlós and E. Szemerédi, A note on Ramsey numbers, J. Combin. Theory Ser. A 29 (1980), 354–360.
N. Alon, On the number of subgraphs of prescribed type of graphs with a given number of edges, Israel J. Math 38 (1981), 116–130.
N. Alon and J. H. Spencer, The Probabilistic Method, 3rd ed., Wiley, 2008.
J. Beck, Achievement games and the probabilistic method, in Combinatorics, Paul Erdős is Eighty, Vol. 1, 51–78, Bolyai Soc. Math. Stud., János Bolyai Math. Soc., Budapest, 1993.
J. Beck, Combinatorial Games: Tic-Tac-Toe Theory, Cambridge University Press, 2008.
T. Bohman, The triangle-free process, Adv. Math. 221 (2009), 1653–1677.
T. Bohman and P. Keevash, The early evolution of the \(H\)-free process, Invent. Math. 181 (2010), 291–336.
T. Bohman and P. Keevash, Dynamic concentration of the triangle-free process, preprint available at arXiv:1302.5963 [math.CO].
D. Conlon, A new upper bound on diagonal Ramsey numbers, Ann. of Math. 170 (2009), 941–960.
D. Conlon, On-line Ramsey numbers, SIAM J. Discrete Math., 23 (2009), 1954–1963.
D. Conlon, J. Fox and B. Sudakov, Hypergraph Ramsey numbers, J. Amer. Math. Soc. 23 (2010), 247–266.
P. Erdős, Graph theory and probability. II, Canad. J. Math., 13 (1961), 346–352.
P. Erdős, R. J. Faudree, C. C. Rousseau and R. H. Schelp, The size Ramsey number, Period. Math. Hungar. 9 (1978), 145–161.
P. Erdős and L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions, in Infinite and finite sets (Colloq., Keszthely, 1973), Vol. II, 609–627, Colloq. Math. Soc. János Bolyai, Vol. 10, North-Holland, Amsterdam, 1975.
P. Erdős and J. Spencer, Lopsided Lovász local lemma and Latin transversals, Discrete Appl. Math. 30 (1991), 151–154.
A. Ferber, M. Krivelevich, B. Sudakov and P. Vieira, Finding Hamilton cycles in random graphs with few queries, Random Structures Algorithms 49 (2016), 635–668.
A. Ferber, M. Krivelevich, B. Sudakov and P. Vieira, Finding paths in sparse random graphs requires many queries, Random Structures Algorithms 50 (2017), 71–85.
G. Fiz Pontiveros, S. Griffiths and R. Morris, The triangle-free process and \(R(3,k)\), to appear, Mem. Amer. Math Soc.
E. Friedgut, Y. Kohayakawa, V. Rödl, A. Ruciński and P. Tetali, Ramsey games against a one-armed bandit, Combin. Probab. Comput. 12 (2003), 515–545.
D. Hefetz, M. Krivelevich, M. Stojakovic and T. Szabó, Positional Games, Birkhäuser, 2014.
J. H. Kim, The Ramsey number \(R(3, t)\) has order of magnitude \(t^2/\log t\), Random Structures Algorithms 7 (1995), 173–207.
M. Krivelevich, Bounding Ramsey numbers through large deviation inequalities, Random Structures Algorithms 7 (1995), 145–155.
M. Krivelevich, Positional games, in Proceedings of the International Congress of Mathematicians, Vol. 4, 355–379, Kyung Moon Sa, Seoul, 2014.
M. Krivelevich and B. Sudakov, Pseudo-random graphs, in More sets, graphs and numbers, 199–262, Bolyai Soc. Math. Stud., 15, Springer, Berlin, 2006.
A. Kurek and A. Ruciński, Two variants of the size Ramsey number, Discuss. Math. Graph Theory 25 (2005), 141–149.
J. Spencer, Ramsey’s theorem – a new lower bound, J. Combin. Theory Ser. A 18 (1975), 108–115.
Acknowledgements
The first author’s research is supported by a Royal Society University Research Fellowship and by ERC Starting Grant 676632. The second author’s research is supported by a Packard Fellowship and by NSF Career Award DMS-1352121. The fourth author’s research is supported by a NSF Graduate Research Fellowship DGE-1656518. We are extremely grateful to Joel Spencer for pointing out a serious flaw in our previous proof of Theorem 1.4 which had been based on a generalization of the Lovász Local Lemma [15]. In the current version, we have a correct proof using a different approach. We would also like to thank the referee for some helpful remarks and Benny Sudakov for bringing the paper of Krivelevich [22] to our attention.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 János Bolyai Mathematical Society and Springer-Verlag GmbH Germany, part of Springer Nature
About this chapter
Cite this chapter
Conlon, D., Fox, J., Grinshpun, A., He, X. (2019). Online Ramsey Numbers and the Subgraph Query Problem. In: Bárány, I., Katona, G., Sali, A. (eds) Building Bridges II. Bolyai Society Mathematical Studies, vol 28. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-59204-5_4
Download citation
DOI: https://doi.org/10.1007/978-3-662-59204-5_4
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-59203-8
Online ISBN: 978-3-662-59204-5
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)