A Caltech Library Service

Online Ramsey Numbers and the Subgraph Query Problem

Conlon, David and Fox, Jacob and Grinshpun, Andrey and He, Xiaoyu (2018) Online Ramsey Numbers and the Subgraph Query Problem. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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 [equation; see abstract in PDF for details] 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 [equation; see abstract in PDF for details] for the lower bound on the diagonal online Ramsey number, as well as a corresponding improvement [equation; see abstract in PDF for details] for the off-diagonal case, where m ≥ 3 is fixed and n → ∞. Using a different randomized Painter strategy, we prove that [equation; see abstract in PDF for details], determining this function up to a polylogarithmic factor. We also improve the upper bound in the off-diagonal case for m ≥ 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.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Conlon, David0000-0001-5899-1829
Additional Information:Conlon research supported by a Royal Society University Research Fellowship and by ERC Starting Grant 676632. Fox research supported by a Packard Fellowship and by NSF Career Award DMS-1352121. We are extremely grateful to Joel Spencer for pointing out a serious flaw in our previous proof of Theorem 4 which had been based on a generalization of the Lovász Local Lemma [P. Erdős and J. Spencer, Lopsided Lovász local lemma and Latin transversals, Discrete Appl. Math. 30 (1991), 151–154]. In the current version, we have a correct proof using a different approach. We would also like to thank the anonymous referee for some helpful remarks and Benny Sudakov for bringing the paper of Krivelevich [Bounding Ramsey numbers through large deviation inequalities, Random Structures Algorithms 7 (1995), 145–155] to our attention.
Funding AgencyGrant Number
European Research Council (ERC)676632
David and Lucile Packard FoundationUNSPECIFIED
Record Number:CaltechAUTHORS:20190819-170917920
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:98028
Deposited By: Melissa Ray
Deposited On:20 Aug 2019 21:26
Last Modified:03 Oct 2019 21:37

Repository Staff Only: item control page