{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T04:05:32Z","timestamp":1745985932668,"version":"3.40.4"},"reference-count":29,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2024,12,13]],"date-time":"2024-12-13T00:00:00Z","timestamp":1734048000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2025,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper we consider positional games where the winning sets are edge sets of tree-universal graphs. Specifically, we show that in the unbiased Maker-Breaker game on the edges of the complete graph <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000397_inline1.png\"\/><jats:tex-math>\n$K_n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, Maker has a strategy to claim a graph which contains copies of all spanning trees with maximum degree at most <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000397_inline2.png\"\/><jats:tex-math>\n$cn\/\\log (n)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, for a suitable constant <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000397_inline3.png\"\/><jats:tex-math>\n$c$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000397_inline4.png\"\/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> being large enough. We also prove an analogous result for Waiter-Client games. Both of our results show that the building player can play at least as good as suggested by the random graph intuition. Moreover, they improve on a special case of earlier results by Johannsen, Krivelevich, and Samotij as well as Han and Yang for Maker-Breaker games.<\/jats:p>","DOI":"10.1017\/s0963548324000397","type":"journal-article","created":{"date-parts":[[2024,12,13]],"date-time":"2024-12-13T13:23:49Z","timestamp":1734096229000},"page":"338-358","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Tree universality in positional games"],"prefix":"10.1017","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0381-0351","authenticated-orcid":false,"given":"Grzegorz","family":"Adamski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7868-2791","authenticated-orcid":false,"given":"Sylwia","family":"Antoniuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3800-0503","authenticated-orcid":false,"given":"Ma\u0142gorzata","family":"Bednarska-Bzd\u0229ga","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5940-6556","authenticated-orcid":false,"given":"Dennis","family":"Clemens","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7166-1437","authenticated-orcid":false,"given":"Fabian","family":"Hamann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4239-9112","authenticated-orcid":false,"given":"Yannick","family":"Mogge","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2024,12,13]]},"reference":[{"volume-title":"Random Graphs","year":"2011","author":"Janson","key":"S0963548324000397_ref23"},{"key":"S0963548324000397_ref12","first-page":"1","article-title":"Client-Waiter games on complete and random graphs","volume":"23","author":"Dean","year":"2016","journal-title":"Electron. J. Comb."},{"volume-title":"Introduction to Graph Theory","year":"2001","author":"West","key":"S0963548324000397_ref29"},{"key":"S0963548324000397_ref28","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(91)90025-W"},{"key":"S0963548324000397_ref24","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000533"},{"key":"S0963548324000397_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70335-2"},{"key":"S0963548324000397_ref19","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.04.001"},{"key":"S0963548324000397_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2022.113191"},{"key":"S0963548324000397_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2023.113478"},{"key":"S0963548324000397_ref25","doi-asserted-by":"publisher","DOI":"10.1137\/100805753"},{"key":"S0963548324000397_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2009.03.051"},{"key":"S0963548324000397_ref27","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2021.10.001"},{"key":"S0963548324000397_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-0825-5"},{"key":"S0963548324000397_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(73)90005-8"},{"key":"S0963548324000397_ref18","doi-asserted-by":"publisher","DOI":"10.1002\/1097-0118(200103)36:3<121::AID-JGT1000>3.0.CO;2-U"},{"key":"S0963548324000397_ref4","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511735202"},{"key":"S0963548324000397_ref26","doi-asserted-by":"publisher","DOI":"10.1137\/0112059"},{"key":"S0963548324000397_ref5","doi-asserted-by":"crossref","unstructured":"[5] Bednarska-Bzd\u0229ga, M. (2013) On weight function methods in Chooser\u2013Picker games. Theor. Comput. Sci. 475 21\u201333","DOI":"10.1016\/j.tcs.2012.12.037"},{"key":"S0963548324000397_ref10","first-page":"1","article-title":"Fast strategies in Waiter-Client games","volume":"27","author":"Clemens","year":"2020","journal-title":"Electron. J. Comb."},{"key":"S0963548324000397_ref1","unstructured":"[1] Adamski, G. , Antoniuk, S. , Bednarska-Bzd\u0229ga, M. , Clemens, D. , Hamann, F. and Mogge, Y. (2024) Creating spanning trees in Waiter-Client games, arXiv preprint arXiv: 2403.18534."},{"key":"S0963548324000397_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000375"},{"key":"S0963548324000397_ref8","doi-asserted-by":"publisher","DOI":"10.1137\/140976054"},{"key":"S0963548324000397_ref17","unstructured":"[17] Han, J. and Yang, D. (2022) Spanning trees in sparse expanders, arXiv preprint arXiv: 2211.04758."},{"key":"S0963548324000397_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2015.12.020"},{"key":"S0963548324000397_ref2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20280"},{"key":"S0963548324000397_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2012.01.007"},{"key":"S0963548324000397_ref20","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20252"},{"key":"S0963548324000397_ref16","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20279"},{"key":"S0963548324000397_ref6","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548315000310"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548324000397","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T05:00:46Z","timestamp":1745902846000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548324000397\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,13]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,5]]}},"alternative-id":["S0963548324000397"],"URL":"https:\/\/doi.org\/10.1017\/s0963548324000397","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2024,12,13]]},"assertion":[{"value":"\u00a9 The Author(s), 2024. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}