On-line Ramsey Numbers
From MaRDI portal
Publication:3058538
DOI10.1137/090749220zbMATH Open1213.05177arXiv0902.1715OpenAlexW2060194042MaRDI QIDQ3058538FDOQ3058538
Authors: David Conlon 
Publication date: 3 December 2010
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Abstract: Consider the following game between two players, Builder and Painter. Builder draws edges one at a time and Painter colours them, in either red or blue, as each appears. Builder's aim is to force Painter to draw a monochromatic copy of a fixed graph G. The minimum number of edges which Builder must draw, regardless of Painter's strategy, in order to guarantee that this happens is known as the on-line Ramsey number ilde{r}(G) of G. Our main result, relating to the conjecture that ilde{r}(K_t) = o(�inom{r(t)}{2}), is that there exists a constant c > 1 such that ilde{r}(K_t) leq c^{-t} �inom{r(t)}{2} for infinitely many values of t. We also prove a more specific upper bound for this number, showing that there exists a constant c such that ilde{r}(K_t) leq t^{-c frac{log t}{log log t}} 4^t. Finally, we prove a new upper bound for the on-line Ramsey number of the complete bipartite graph K_{t,t}.
Full work available at URL: https://arxiv.org/abs/0902.1715
Recommendations
- On-line Ramsey theory
- Online and size anti-Ramsey numbers
- On-line Ramsey numbers of paths and cycles
- On-line Ramsey numbers for paths and stars
- Small on-line Ramsey numbers -- a new approach
- The on-line degree Ramsey number of cycles
- On-line Ramsey numbers for paths and short cycles
- Online Ramsey numbers and the subgraph query problem
- An upper bound for the restricted online Ramsey number
- A note on on-line Ramsey numbers for quadrilaterals
Cited In (29)
- Online Ramsey numbers and the subgraph query problem
- A note on on-line Ramsey numbers of stars and paths
- On-line Ramsey numbers for paths and short cycles
- Proper colouring painter-builder game
- Online size Ramsey numbers: odd cycles vs connected graphs
- Coloring random graphs online without creating monochromatic subgraphs
- On the computational complexity and strategies of online Ramsey theory
- Online Ramsey theory for planar graphs
- On-line Ramsey theory for bounded degree graphs
- A note on restricted online Ramsey numbers of matchings
- Trees with an on-line degree Ramsey number of four
- A strengthening of the Erdős-Szekeres theorem
- Restricted online Ramsey numbers of matchings and trees
- An upper bound for the restricted online Ramsey number
- Small on-line Ramsey numbers -- a new approach
- On-line Ramsey numbers of paths and cycles
- Bounds on Ramsey games via alterations
- Guessing fractions of online sequences
- Biclique-colouring verification complexity and biclique-colouring power graphs
- Online Ramsey numbers: long versus short cycles
- On-line size Ramsey number for monotone \(k\)-uniform ordered paths with uniform looseness
- Size Gallai-Ramsey number
- Interview with David Conlon
- Online Ramsey numbers of ordered paths and cycles
- On-line Ramsey numbers for paths and stars
- A note on on-line Ramsey numbers for quadrilaterals
- A combinatorial game over biclique-hypergraphs of powers of paths and of powers of cycles through monochromatic transversals
- Coloring number and on-line Ramsey theory for graphs and hypergraphs
- The on-line degree Ramsey number of cycles
This page was built for publication: On-line Ramsey Numbers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3058538)
