Online Ramsey numbers and the Subgraph Query Problem
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 Km or a blue...
| Glavni autori: | , , , |
|---|---|
| Format: | Conference item |
| Izdano: |
Springer
2019
|
| _version_ | 1826270996797063168 |
|---|---|
| author | Conlon, D Fox, J Grinshpun, A He, X |
| author_facet | Conlon, D Fox, J Grinshpun, A He, X |
| author_sort | Conlon, D |
| collection | OXFORD |
| description | 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 Km or a blue Kn using as few turns as possible. The online Ramsey number ~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 ~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 m ≥ 3 is fixed and n → ∞. Using a different randomized Painter strategy, we prove that ~r(3; n) = ~0(n3), 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 Erdos–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. |
| first_indexed | 2024-03-06T21:49:40Z |
| format | Conference item |
| id | oxford-uuid:4acf63d2-4890-4f97-80f0-370362e91f02 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T21:49:40Z |
| publishDate | 2019 |
| publisher | Springer |
| record_format | dspace |
| spelling | oxford-uuid:4acf63d2-4890-4f97-80f0-370362e91f022022-03-26T15:39:47ZOnline Ramsey numbers and the Subgraph Query ProblemConference itemhttp://purl.org/coar/resource_type/c_5794uuid:4acf63d2-4890-4f97-80f0-370362e91f02Symplectic Elements at OxfordSpringer2019Conlon, DFox, JGrinshpun, AHe, XThe (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 Km or a blue Kn using as few turns as possible. The online Ramsey number ~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 ~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 m ≥ 3 is fixed and n → ∞. Using a different randomized Painter strategy, we prove that ~r(3; n) = ~0(n3), 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 Erdos–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. |
| spellingShingle | Conlon, D Fox, J Grinshpun, A He, X Online Ramsey numbers and the Subgraph Query Problem |
| title | Online Ramsey numbers and the Subgraph Query Problem |
| title_full | Online Ramsey numbers and the Subgraph Query Problem |
| title_fullStr | Online Ramsey numbers and the Subgraph Query Problem |
| title_full_unstemmed | Online Ramsey numbers and the Subgraph Query Problem |
| title_short | Online Ramsey numbers and the Subgraph Query Problem |
| title_sort | online ramsey numbers and the subgraph query problem |
| work_keys_str_mv | AT conlond onlineramseynumbersandthesubgraphqueryproblem AT foxj onlineramseynumbersandthesubgraphqueryproblem AT grinshpuna onlineramseynumbersandthesubgraphqueryproblem AT hex onlineramseynumbersandthesubgraphqueryproblem |