On-line Ramsey Numbers
- Creators
-
Conlon, David
Abstract
Consider the following game between two players, Builder and Painter. Builder draws edges one at a time and Painter colors 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 ˜r(G) of G. Our main result, relating to the conjecture that [equation; see abstract in PDF for details], is that there exists a constant c > 1 such that [equation; see abstract in PDF for details] for infinitely many values of t. We also prove a more specific upper bound for this number, showing that there exists a positive constant c such that [equation; see abstract in PDF for details]. Finally, we prove a new upper bound for the on-line Ramsey number of the complete bipartite graph K_(t,t).
Additional Information
© 2009 Society for Industrial and Applied Mathematics. Submitted 10 February 2009; accepted 08 September 2009; published online 11 December 2009. The author was supported by a Junior Research Fellowship at St. John's College, Cambridge. I would like to thank Jacob Fox for reading carefully through an earlier version of this paper and making several helpful suggestions.Attached Files
Published - 090749220.pdf
Submitted - 0902.1715.pdf
Files
| Name | Size | Download all |
|---|---|---|
|
md5:ff684cd5300ebc7ce5de0b624e921660
|
151.8 kB | Preview Download |
|
md5:e33e3a186b476d28074e93cf3c7c1ee1
|
160.1 kB | Preview Download |
Additional details
- Eprint ID
- 97814
- Resolver ID
- CaltechAUTHORS:20190812-162958058
- St. John's College, Cambridge
- Created
-
2019-08-15Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field