{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T15:00:06Z","timestamp":1776697206480,"version":"3.51.2"},"reference-count":0,"publisher":"Cambridge University Press (CUP)","issue":"5-6","license":[{"start":{"date-parts":[[2003,12,3]],"date-time":"2003-12-03T00:00:00Z","timestamp":1070409600000},"content-version":"unspecified","delay-in-days":32,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2003,11]]},"abstract":"<jats:p>We study the following one-person game against a random graph process: the Player's goal is to 2-colour a random sequence of edges <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" mimetype=\"image\" xlink:href=\"S0963548303005881_inline1.png\"\/> of a complete graph on <jats:italic>n<\/jats:italic> vertices, avoiding a monochromatic triangle for as long as possible. The game is over when a monochromatic triangle is created. The online version of the game requires that the Player should colour each edge as it comes, before looking at the next edge.<\/jats:p><jats:p>While it is not hard to prove that the expected length of this game is about <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" mimetype=\"image\" xlink:href=\"S0963548303005881_inline2.png\"\/>, the proof of the upper bound suggests the following relaxation: instead of colouring online, the random graph is generated in only two rounds, and the Player colours the edges of the first round before the edges of the second round are thrown in. Given the size of the first round, how many edges can there be in the second round for the Player to be likely to win? In the extreme case, when the first round consists of a random graph with <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" mimetype=\"image\" xlink:href=\"S0963548303005881_inline3.png\"\/> edges, where <jats:italic>c<\/jats:italic> is a positive constant, we show that the Player can win with high probability only if <jats:italic>constantly<\/jats:italic> many edges are generated in the second round.<\/jats:p>","DOI":"10.1017\/s0963548303005881","type":"journal-article","created":{"date-parts":[[2003,12,3]],"date-time":"2003-12-03T14:23:14Z","timestamp":1070461394000},"page":"515-545","source":"Crossref","is-referenced-by-count":25,"title":["Ramsey Games Against a One-Armed Bandit"],"prefix":"10.1017","volume":"12","author":[{"given":"Ehud","family":"Friedgut","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yoshiharu","family":"Kohayakawa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vojt\u011bch","family":"Rodl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Rucinski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Prasad","family":"Tetali","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2003,12,3]]},"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548303005881","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,15]],"date-time":"2020-05-15T09:22:34Z","timestamp":1589534554000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548303005881\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,11]]},"references-count":0,"journal-issue":{"issue":"5-6","published-print":{"date-parts":[[2003,11]]}},"alternative-id":["S0963548303005881"],"URL":"https:\/\/doi.org\/10.1017\/s0963548303005881","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,11]]}}}