{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T04:05:29Z","timestamp":1770696329208,"version":"3.49.0"},"reference-count":29,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2013,6,11]],"date-time":"2013-06-11T00:00:00Z","timestamp":1370908800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2013,7]]},"abstract":"<jats:p>We study Maker\/Breaker games on the edges of<jats:italic>sparse<\/jats:italic>graphs. Maker and Breaker take turns at claiming previously unclaimed edges of a given graph<jats:italic>H<\/jats:italic>. Maker aims to occupy a given target graph<jats:italic>G<\/jats:italic>and Breaker tries to prevent Maker from achieving his goal. We show that for every<jats:italic>d<\/jats:italic>there is a constant<jats:italic>c<\/jats:italic>=<jats:italic>c(d)<\/jats:italic>with the property that for every graph<jats:italic>G<\/jats:italic>on<jats:italic>n<\/jats:italic>vertices of maximum degree<jats:italic>d<\/jats:italic>there is a graph<jats:italic>H<\/jats:italic>on at most<jats:italic>cn<\/jats:italic>edges such that Maker has a strategy to occupy a copy of<jats:italic>G<\/jats:italic>in the game on<jats:italic>H<\/jats:italic>.<\/jats:p><jats:p>This is a result about a game-theoretic variant of the size Ramsey number. For a given graph<jats:italic>G<\/jats:italic>,<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548313000151_inline1\"\/><jats:tex-math>$\\hat{r}'(G)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>is defined as the smallest number<jats:italic>M<\/jats:italic>for which there exists a graph<jats:italic>H<\/jats:italic>with<jats:italic>M<\/jats:italic>edges such that Maker has a strategy to occupy a copy of<jats:italic>G<\/jats:italic>in the game on<jats:italic>H<\/jats:italic>. In this language, our result yields that for every connected graph<jats:italic>G<\/jats:italic>of constant maximum degree,<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548313000151_inline2\"\/><jats:tex-math>$\\hat{r}'(G) = \\Theta(n)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p><jats:p>Moreover, we can also use our method to settle the corresponding extremal number for<jats:italic>universal<\/jats:italic>graphs: for a constant<jats:italic>d<\/jats:italic>and for the class<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548313000151_inline3\"\/><jats:tex-math>${\\cal G}_{n}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>of<jats:italic>n<\/jats:italic>-vertex graphs of maximum degree<jats:italic>d<\/jats:italic>,<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548313000151_inline4\"\/><jats:tex-math>$s({\\cal G}_{n})$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>denotes the minimum number such that there exists a graph<jats:italic>H<\/jats:italic>with<jats:italic>M<\/jats:italic>edges where, for<jats:italic>every<\/jats:italic><jats:italic>G<\/jats:italic>\u2208<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548313000151_inline3\"\/><jats:tex-math>${\\cal G}_{n}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, Maker has a strategy to build a copy of<jats:italic>G<\/jats:italic>in the game on<jats:italic>H<\/jats:italic>. We obtain that<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548313000151_inline5\"\/><jats:tex-math>$s({\\cal G}_{n}) = \\Theta(n^{2 - \\frac{2}{d}})$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1017\/s0963548313000151","type":"journal-article","created":{"date-parts":[[2013,6,11]],"date-time":"2013-06-11T09:33:45Z","timestamp":1370943225000},"page":"499-516","source":"Crossref","is-referenced-by-count":2,"title":["Size Ramsey Number of Bounded Degree Graphs for Games"],"prefix":"10.1017","volume":"22","author":[{"given":"HEIDI","family":"GEBAUER","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2013,6,11]]},"reference":[{"key":"S0963548313000151_ref7","first-page":"21","article-title":"On graphs which contain all sparse graphs.","volume":"12","author":"Babai","year":"1982","journal-title":"Ann. Discrete Math."},{"key":"S0963548313000151_ref28","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/s004930070024","article-title":"On size Ramsey numbers of graphs with bounded degree.","volume":"20","author":"R\u00f6dl","year":"2000","journal-title":"Combinatorica"},{"key":"S0963548313000151_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579267"},{"key":"S0963548313000151_ref18","doi-asserted-by":"publisher","DOI":"10.1137\/0604055"},{"key":"S0963548313000151_ref22","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548308009401"},{"key":"S0963548313000151_ref29","unstructured":"Sz\u00e9kely L. A. (1984) On two concepts of discrepancy in a class of combinatorial games. In Infinite and Finite Sets, Vol. 37 of Colloquia Mathematica Societatis Janos Bolyai, pp. 679\u2013683."},{"key":"S0963548313000151_ref3","first-page":"373","volume-title":"Proc. 19th Annual ACM\u2013SIAM Symposium on Discrete Algorithms","author":"Alon","year":"2008"},{"key":"S0963548313000151_ref14","first-page":"741","volume-title":"Proc. 31st Annual ACM Symposium on Theory of Computing","author":"Capalbo","year":"1999"},{"key":"S0963548313000151_ref11","doi-asserted-by":"publisher","DOI":"10.1137\/0402014"},{"key":"S0963548313000151_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(78)90072-2"},{"key":"S0963548313000151_ref16","doi-asserted-by":"publisher","DOI":"10.1111\/j.1749-6632.1979.tb32784.x"},{"key":"S0963548313000151_ref24","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579202"},{"key":"S0963548313000151_ref27","first-page":"225","article-title":"A note on universal graphs.","volume":"11","author":"R\u00f6dl","year":"1981","journal-title":"Ars Combin."},{"key":"S0963548313000151_ref10","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300000936"},{"key":"S0963548313000151_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-0427(01)00455-1"},{"key":"S0963548313000151_ref2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20143"},{"key":"S0963548313000151_ref4","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892007"},{"key":"S0963548313000151_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44666-4_20"},{"key":"S0963548313000151_ref6","doi-asserted-by":"crossref","first-page":"R51","DOI":"10.37236\/1948","article-title":"Discrepancy games","volume":"12","author":"Alon","year":"2005","journal-title":"Electron. J. Combin."},{"key":"S0963548313000151_ref9","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190070115"},{"key":"S0963548313000151_ref17","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-27.2.203"},{"key":"S0963548313000151_ref12","first-page":"95","volume-title":"Advances in Computing Research 2","author":"Bhatt","year":"1984"},{"key":"S0963548313000151_ref19","doi-asserted-by":"crossref","DOI":"10.1201\/9781439863879","volume-title":"Erd\u0151s on Graphs: His Legacy of Unsolved Problems","author":"Chung","year":"1998"},{"key":"S0963548313000151_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(83)90037-0"},{"key":"S0963548313000151_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/BF02018930"},{"key":"S0963548313000151_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2009.03.004"},{"key":"S0963548313000151_ref25","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001619"},{"key":"S0963548313000151_ref26","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2011.01.004"},{"key":"S0963548313000151_ref13","first-page":"150","volume-title":"Proc. 10th Annual ACM\u2013SIAM Symposium on Discrete Algorithms","author":"Capalbo","year":"1999"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548313000151","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,28]],"date-time":"2020-07-28T05:01:14Z","timestamp":1595912474000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548313000151\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6,11]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,7]]}},"alternative-id":["S0963548313000151"],"URL":"https:\/\/doi.org\/10.1017\/s0963548313000151","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,6,11]]}}}