Online Ramsey Numbers and the Subgraph Query Problem
Online Ramsey Numbers and the Subgraph Query Problem
复制标题
在线拉姆齐数和子图查询问题
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Xiaoyu He
中科院分区：
文献类型：
--
作者：
D. Conlon;J. Fox;A. Grinshpun;Xiaoyu He
（m，n）-在线Ramsey博弈是两个参与者Builder和Painter之间的组合博弈。从一组无限的孤立顶点开始，Builder在每个转弯处绘制一条边，Painter立即将其绘制为红色或蓝色。Builder的目标是强制Painter使用尽可能少的回合创建红色（K_m）或蓝色（K_n）。在线Ramsey数（ ilde{r}（m，n））是生成器保证在（m，n）-在线Ramsey游戏中获胜所需的最小边数。通过分析Painter随机播放的特殊情况，我们获得了指数级的改善（ ilde{r}（n，n）ge 2^{（2-sqrt{2}）n + O（1）}）对于对角在线Ramsey数的下界，以及相应的改进（ ilde{r}（m，n）ge n^{（2-sqrt{2}）m + O（1）}），其中（mge 3）是固定的，并且（n
八箭头infty）。使用一个不同的随机画家策略，我们证明（ ilde{r}（3，n）= ilde{Theta }（n^3）），确定该函数的多对数因子。我们还提高了上界的非对角的情况下（m ge 4）。在与一个随机画家的在线拉姆齐游戏，我们研究的问题，找到一个副本的目标图H在一个足够大的未知Erdens-Renyi随机图G（N，p）使用尽可能少的查询，其中每个查询揭示是否一个特定的顶点对相邻。我们称这个问题为子图查询问题。我们确定的顺序的查询的数量需要完整的图到五个顶点，并证明这个问题的一般界限。
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 ( ilde{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 ( ilde{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 ( ilde{r}(m,n) ge n^{(2-sqrt{2})m + O(1)}) for the off-diagonal case, where (mge 3) is fixed and (n
ightarrow infty ). Using a different randomized Painter strategy, we prove that ( ilde{r}(3,n)= ilde{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–Renyi 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.